leetcode 494
来源：9-7 面试中的0-1背包问题 Partition Equal Subset Sum
慕哥6062902
2023-09-06
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的定义都不是很清楚，能请帮忙解释下吗
1回答
-
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]; } }请根据这个问题，再仔细理解一下，我在课程中强调的，明确程序中的变量语义的意思。语义的定义你可以变，但一旦改变，所有的逻辑，都是围绕语义进行的（而非先写逻辑，再去考虑语义。）
继续加油！：）
032023-09-08
相似问题