最小化目标值与所选元素的差

标签: 数组 动态规划 矩阵

难度: Medium

给你一个大小为 m x n 的整数矩阵 mat 和一个整数 target 。

从矩阵的 每一行 中选择一个整数，你的目标是 最小化 所有选中元素之 和 与目标值 target 的 绝对差 。

返回 最小的绝对差 。

a 和 b 两数字的 绝对差 是 a - b 的绝对值。

示例 1：

输入：mat = [[1,2,3],[4,5,6],[7,8,9]], target = 13
输出：0
解释：一种可能的最优选择方案是：
- 第一行选出 1
- 第二行选出 5
- 第三行选出 7
所选元素的和是 13 ，等于目标值，所以绝对差是 0 。

示例 2：

输入：mat = [[1],[2],[3]], target = 100
输出：94
解释：唯一一种选择方案是：
- 第一行选出 1
- 第二行选出 2
- 第三行选出 3
所选元素的和是 6 ，绝对差是 94 。

示例 3：

输入：mat = [[1,2,9,8,7]], target = 6
输出：1
解释：最优的选择方案是选出第一行的 7 。
绝对差是 1 。

提示：

  • m == mat.length
  • n == mat[i].length
  • 1 <= m, n <= 70
  • 1 <= mat[i][j] <= 70
  • 1 <= target <= 800

Submission

运行时间: 53 ms

内存: 16.3 MB

# class Solution:
#     def minimizeTheDifference(self, mat: List[List[int]], target: int) -> int:
#         m, n = len(mat), len(mat[0])
#         # 什么都不选时和为 0
#         f = {0}
#         # 最小的大于等于 target 的和
#         large = float("inf")
#         for i in range(m):
#             g = set()
#             next_large = float("inf")
#             for x in mat[i]:
#                 for j in f:
#                     if j + x >= target:
#                         next_large = min(next_large, j + x)
#                     else:
#                         g.add(j + x)
#                 next_large = min(next_large, large + x)
#             f = g
#             large = next_large
        
#         ans = abs(large - target)
#         for x in f:
#             ans = min(ans, abs(x - target))
#         return ans
class Solution:
    def minimizeTheDifference(self, mat: List[List[int]], target: int) -> int:
        bits=1
        for row in mat:
            tmp=0
            for r in row:
                tmp |= (bits<<r)
            bits=tmp
        # print(bits)
        ans=inf
        for i in range(target,4901,1):
            if bits &(1<<i):
                ans=min(ans,i-target)
                break
        for i in range(target,-1,-1):
            if bits &(1<<i):
                ans=min(ans,target-i)
                break
        return ans

Explain

题解采用了动态规划的思想，结合状态压缩的技术来解决问题。核心思路是使用位运算的技巧，通过整数的每一位来表示某个和是否可达。具体步骤如下： 1. 初始状态`bits`设为1，表示只有和为0是可达的。 2. 遍历矩阵的每一行，对于每个元素，更新可达和的状态。这是通过将`bits`左移元素值位，然后与原`bits`做或运算实现的。 3. 最后，在所有可能的和中，找到最接近target的值，计算其与target的差值。

时间复杂度: O(m * n + 4900)

空间复杂度: O(1)

# class Solution:
#     def minimizeTheDifference(self, mat: List[List[int]], target: int) -> int:
        # 初始化bits，只有和为0是可达的
        bits = 1
        # 遍历矩阵的每一行
        for row in mat:
            tmp = 0
            # 遍历行中的每一个元素
            for r in row:
                # 更新可达和的状态
                tmp |= (bits << r)
            bits = tmp
        # 初始化答案为无穷大
        ans = float('inf')
        # 寻找大于等于target的最小可达和
        for i in range(target, 4901):
            if bits & (1 << i):
                ans = min(ans, i - target)
                break
        # 寻找小于target的最大可达和
        for i in range(target, -1, -1):
            if bits & (1 << i):
                ans = min(ans, target - i)
                break
        return ans

Explore

位运算可以更加高效地存储和处理状态信息。使用位运算（特别是位向量），每个比特(bit)可以代表一个状态（例如和是否可达），这样可以极大地节省空间，同时位运算（如与、或、左移）都是非常快速的操作，特别适合用于需要频繁更新状态的动态规划问题。相比之下，使用数组或哈希表虽然在逻辑上更直观，但在空间和操作效率上可能不如位运算优越。

在动态规划中，每一步的`bits`表示当前所有可达的和。当将`bits`左移一个元素的值r位时，原本可达的和x变成了x+r，这代表和x+r现在也是可达的。通过对所有可能的x执行这样的操作，我们可以得到所有通过加上该元素后可能达到的和。将这个结果与原本的`bits`做或运算，意味着合并新的可达和与原有的可达和，确保所有之前和新增的可达和都被记录。

最大可能和4900是基于矩阵的最大行数和每个元素的最大可能值估算得出的。假设矩阵的每一行都选择了最大值，而没有给出具体的矩阵规模与元素大小限制，常见的假设是每个元素的大小不会超过100，如果矩阵有最多70行（这是一个假设的常见行数上限），则最大可能和为70*100=7000。4900可能是一个估计或特定问题设定下的值。如果矩阵行数或元素大小有不同，这个数字可能需要调整。

直接寻找最接近target的可达和在理论上是可行的，但在实现时可能需要更复杂的逻辑来同时处理大于和小于target的情况。通过分别向上和向下寻找，可以简化逻辑：先找到第一个大于等于target的可达和，然后找到最大的小于等于target的可达和，这两个值保证了覆盖所有接近target的情况。这种方法可以更系统地确保找到真正的最小绝对差，尤其是在状态空间大而稀疏时更有效。