LeetCode最小化目标和差值题是否存在重叠子问题适合DP求解

问题解答 #

1. 重叠子问题真实存在 #

你认为「所有元素都是正数就不会出现重复sum」的认知是错误的，不同的选数路径完全可以得到相同的前缀和，举个简单的例子：
假设前两行的矩阵为[[1,4],[2,3]]：

• 路径1：第一行选1、第二行选3，前缀和为1+3=4
• 路径2：第一行选4、第二行选2，前缀和为4+2=4

当处理到第三行（i=2）时，两个不同的路径都会进入i=2, sum=4的状态，这就是典型的重叠子问题，此时第二次进入该状态时就可以直接复用之前计算好的dp[2][4]结果，不需要重复递归计算后续的最优解。
你在样例中没有触发cout输出，只是因为样例结构太简单，没有出现重复前缀和的场景，换上面这种结构的测试用例就能触发调试输出。

2. 动态规划的合理性 #

这个DP方案满足算法生效的两个核心要求：

• 无后效性：dp[i][sum]的定义是「处理完前i行、当前前缀和为sum时，选完剩余所有行能得到的最小绝对差值」，不管前面是通过什么路径凑出sum的，后续的最优解只和i和sum两个参数有关，和前面的选择过程无关。
• 重叠子问题：如上所述，不同选法可以得到相同的前缀和，重复计算可以通过缓存DP状态避免。

3. 题解优化说明 #

题解里的两个操作都是为了降低计算量，不影响DP的核心逻辑：

• 每一行转set：去掉同一行的重复元素，避免同一行相同值的重复计算
• 循环break条件：因为set是升序排列，一旦当前元素加sum超过target，后面更大的元素加sum只会离target更远，没必要继续遍历；如果已经得到差值为0的结果，直接终止即可，不可能有更小的差值。

内容的提问来源于stack exchange，提问作者Someone