What is the main strategy for minimizing the difference to the target?

Use state transition dynamic programming with a set to track all possible sums row by row and select the sum closest to the target.

Can this problem be solved with simple recursion?

Recursion without memoization leads to exponential time; DP with sets efficiently prunes redundant sum combinations.

Why is a set used instead of a list for storing sums?

A set avoids duplicates, reducing memory usage and ensuring each reachable sum is considered only once in DP transitions.

How do constraints affect the DP approach?

Since m, n, and values are limited, the maximum sum is bounded, allowing the DP with sets to remain efficient without exploring all combinations.

Does this problem always require full matrix exploration?

No, using state transition DP with sum sets avoids exhaustive search while still capturing all reachable sums to minimize the absolute difference.

#1981

Medium

auto_awesome状态·转移·动态规划

LeetCode 题解工作台

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

给你一个大小为 m x n 的整数矩阵 mat 和一个整数 target 。从矩阵的每一行中选择一个整数，你的目标是最小化所有选中元素之和与目标值 target 的绝对差。返回最小的绝对差。 a 和 b 两数字的绝对差是 a - b 的绝对值。示例 1：输入： mat…

数组动态规划矩阵

题目描述

给你一个大小为 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

lightbulb

解题思路

方法一：动态规划（分组背包）

设 $f[i][j]$ 表示前 $i$ 行是否能选出元素和为 $j$ ，则有状态转移方程：

f[i][j] = \begin{cases} 1 & \textit{如果存在 } x \in row[i] \textit{ 使得 } f[i - 1][j - x] = 1 \\ 0 & \textit{否则} \end{cases}

其中 $row[i]$ 表示第 $i$ 行的元素集合。

由于 $f[i][j]$ 只与 $f[i - 1][j]$ 有关，因此我们可以使用滚动数组优化空间复杂度。

最后，遍历 $f$ 数组，找出最小的绝对差即可。

时间复杂度 $O(m^2 \times n \times C)$ ，空间复杂度 $O(m \times C)$ 。其中 $m$ 和 $n$ 分别为矩阵的行数和列数；而 $C$ 为矩阵元素的最大值。

1

2

3

4

5

6

7

class Solution:
    def minimizeTheDifference(self, mat: List[List[int]], target: int) -> int:
        f = {0}
        for row in mat:
            f = set(a + b for a in f for b in row)
        return min(abs(v - target) for v in f)

speed

复杂度分析

指标	值
时间	and space complexity depend on the range of sums tracked. Using a set to store reachable sums avoids redundant calculations. Worst-case complexity grows with m, n, and the possible sum range, but pruning with sets ensures feasible performance for the given constraints.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
They expect an understanding of state transition DP applied to multiple rows of a matrix.
question_mark
They look for an efficient approach to track reachable sums without generating all combinations explicitly.
question_mark
They may ask about trade-offs between time and space when storing intermediate sums in a set.

warning

常见陷阱

外企场景

error
Attempting to generate all possible combinations leads to exponential time and memory usage.
error
Failing to update the set properly row by row can miss valid sums.
error
Not considering the absolute difference correctly at the end may produce wrong results.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Maximize the sum not exceeding the target by adapting the DP update logic.
arrow_right_alt
Handle negative numbers in the matrix by expanding the sum range tracked in the set.
arrow_right_alt
Find the number of selections achieving the minimal difference instead of the difference itself.

help

常见问题

外企场景

继续练习

#1937 扣分后的最大得分 #2088 统计农场中肥沃金字塔的数目 #1728 猫和老鼠 II