leetcode 494

Question

public int findTargetSumWays(int[] nums, int target) {

        int sum = 0;
        for(int num: nums) sum += num;

        if(target < -sum || target > sum) return 0;

        int n = nums.length;
        int[][] dp = new int[n + 1][2 * sum + 1];

        int offset = sum;
        dp[0][0 + offset] = 1;
        for(int i = 0; i < n; i ++){
            for(int s = -sum; s <= sum; s ++){
                if(-sum <= s + nums[i] && s + nums[i] <= sum)
                    dp[i + 1][s + offset] += dp[i][s + nums[i] + offset];
                if(-sum <= s - nums[i] && s - nums[i] <= sum)
                    dp[i + 1][s + offset] += dp[i][s - nums[i] + offset];
            }
        }
        return dp[n][target + offset];
    }

bobo老师，上面是你的解法，我看懂了dp方程是这么列出来的
dp[i][j] = dp[i-1][j - nums[i]] + dp[i - 1][j + nums[i]];
可是有个地方我不理解：dp的行 为什么需要是n+1？
我本来尝试这么定义,dp[i][j]表示前面nums[0,i]个元素，组成背包容量是j的方法数，那么求的就是dp[nums.length - 1][target]
最后发现结果是错的，然后打印二者的差别，发现我这样写的话实际上会少算一行，必须dp的行是n+1，且遍历的时候，外层for循环必须要遍历到nums.length结束。我想不明白是什么原因，感觉自己对dp的定义都不是很清楚，能请帮忙解释下吗

Answer 1

liuyubobobo 2023-09-07 01:33:57

dp[i][j + offset] 的意思是：使用了 i 个数字，构成表达式的值是 j 的方法数。

因为一共有 n 个数字，所以最终结果就是 dp[n][target + offset]。

也正因为如此，初始 dp[0][0 + target] = 1，即使用 0 个数字（一个数字都不用），有一种方式（就是一个数字都不拿）。

所以，你可以看见，我的代码中的 for 循环里，循环到 i 的时候，求的是 dp[i + 1][s + offset]，为什么是 i + 1，因为使用到索引为 i 的元素，对应使用了  i + 1 个元素。（看索引为 0 的元素，使用了 1 个数字；看索引为 1 的元素，使用了  2 个元素；看索引为 n - 1 的元素，使用了 n 个元素。）

==========

你完全可以把 dp[i][j +offset] 的定义修改成，看到索引为 i 的元素的时候，构成表达式的值是 j 的方法数。（请仔细区分这个定义和我上面叙述的定义的不同）。

如果这样定义，最终结果就是 dp[n - 1][target + offset]。

但是，逻辑需要稍许变换。（更准确的说，是初始化需要变化。）  

请先自己理解上面的叙述以后，自己尝试一下。

下面是参考代码：

class Solution {
    
    public int findTargetSumWays(int[] nums, int target) {
        
        int sum = 0;
        for(int num: nums) sum += num;
        if(target < -sum || target > sum) return 0;
        
        int n = nums.length;
        int[][] dp = new int[n][2 * sum + 1];
        
        
        int offset = sum;
        
        // 注意：为什么初始化变了？
        dp[0][nums[0]+ offset] = 1;
        dp[0][-nums[0]+ offset] += 1;
        
        // 注意，i 为什么是从 1 开始了？
        for(int i = 1; i < n; i ++){
            for(int s = -sum; s <= sum; s ++){
            
                // 注意，为什么计算的是 dp[i][s + offset]? 
                // 而不是 dp[i + 1][s + offset]
                if(-sum <= s + nums[i] && s + nums[i] <= sum)
                    dp[i][s + offset] += dp[i - 1][s + nums[i] + offset];
                if(-sum <= s - nums[i] && s - nums[i] <= sum)
                    dp[i][s + offset] += dp[i - 1][s - nums[i] + offset];
            }
        }
        
        // 注意，为什么返回的是 dp[n - 1][target + offset]
        // 而不是 dp[n][target + offset]
        return dp[n - 1][target + offset];
    }
}

请根据这个问题，再仔细理解一下，我在课程中强调的，明确程序中的变量语义的意思。语义的定义你可以变，但一旦改变，所有的逻辑，都是围绕语义进行的（而非先写逻辑，再去考虑语义。）

继续加油！：）

• 提问者 慕哥6062902 #1

  感谢老师细心讲解，不好意思我一开始的表述不是很准确，你的代码逻辑非常清晰，我是可以理解这样做一定是对的，我最疑惑的点是我使用i表示nums[0,i]，dp[nums.length - 1][target+offset]表示最终所求，这个想法本身是错的导致我得不到正确答案，还是说我的初始化写错（我之前能想到的最大可能问题出在初始化，但是不会改），导致最终结果是错误的。
  谢谢您的详解，原来按照我的想法去定义dp的话，dp[0] 表示 nums[0]已经被选择，那么原本的dp[0][0]含义就变成了dp[0][0 + nums[0]] 和 dp[0][0-nums[0]]，（offset的影响就不说了）也就是我要初始化这两个条件，才等同于您的代码里面只需要初始化dp[0][0];
  然后到这里我可以理解这样的代码
          dp[0][nums[0]+ offset] = 1;
          dp[0][-nums[0]+ offset] = 1;// 原文中是+=
  
  仍然不能理解第二行为什么是 += ，于是我本地调试没问题，提交leetcode后发现通过不了[0,0,0,0,0,0,0,0,1]
  才理解如果nums[0] = 0的话，那实际上正号和负号是两种选择，二者应该叠加。，然后我又回头去看递推公式,把dp[0][0]带进去算的话，确实就应该是+=，也算是验证了递推公式。
  if (Math.abs(j - nums[i]) <= sum) {
                          dp[i][j] += dp[i-1][j - nums[i]];
                      }
                      if (Math.abs(j + nums[i]) <= sum) {
                          dp[i][j] += dp[i-1][j + nums[i]];
                      }
  
  再次感谢讲解，我还想问下，您写代码的时候，一开始就能知道是+=么，还是代入测试用例后，发现了于是改的呢？我想知道是不是要达到一开始就已经从递推公式里面可以得出这里是+=，才算真的理解了这道题，还是说在带入测试用例后，发现了并理解，其实也算是理解了呢

• liuyubobobo 回复 提问者 慕哥6062902 #2

  1）你的总结非常赞。字数不多，但表达的很清晰：）
  
  2）我的新代码的初始化，第二行是 += 的原因，你已经分析的很清晰了。补充一下，其实，把第一行也改成 +=，逻辑也是正确的（想想为什么？）并且我认为或许从“逻辑连贯性”的角度看更好。为什么？因为在下面的循环中，每次计算 dp[i][s + offset] 都是用 +=，即都是从上一个状态加上去。而初始的上一个状态是的值就是 0，+= 1 就是从 0 加上去。
  
  3）通过这个细节，也能看出来我使用第一种定义，初始化 dp[0][0 + offset] = 1 的优点：它没有将 i = 0 的状态做特殊处理，而是将 i = 0 和后续的所有 i 的逻辑统一了。这有点儿类似于链表中加入一个虚拟头结点的效果。很多时候统一逻辑都有这样的优点，不需要对 edge case 做特殊的分析。因为“特殊”的分析很有可能出问题，需要特别小心（但不代表对于所有的 edge case 都有特殊的处理方式。整体上，对于程序设计来说，对 edge case 的处理是普遍且重要的，这就是测试的意义。）
  
  4）如果你使用第二种定义方式，我的 += 其实就是在处理第一个数字是 0 的情况，你也完全可以写成：if(nums[0] == 0) 初始化成 2； else 初始化正负 nums[0] 的逻辑。这在我看来也是思路清晰的。
  
  5）是否考虑到 nums[0] 等于 0 的情况，是这个问题的一个 edge case，个 dp 无关。一开始没有考虑到是非常正常的。不代表你没有理解 dp。但是如果在面试的时候，我喜欢再问一个问题：你可以想象出什么样的测试用例去测试你的代码？当你回答这个问题的时候，一个只有一个数字，并且这个数字是 0，是一个非常好的，同事在我看来也是很“基础”的边界测试用例。但再一次，从面试的角度看，这个问题已经不是再考察你的算法了。
  
  继续加油！：）

• 提问者 慕哥6062902 回复 liuyubobobo #3

  感谢！