划分相等子集和

Question

LC：https://leetcode.com/problems/partition-equal-subset-sum/

所以计算 dp[i][j] 的公式是：

dp[i][j] = dp[i - 1][j - nums[i - 1]] || dp[i - 1][j];

OR 运算符之前的前半部分表示当我们 SELECT 第 I 个元素时发生的情况。

我的问题是为什么是 j - nums[i - 1] 而不是 j - nums[i]。

我们是不是应该用当前的sum(j)减去第i个元素的当前'weight'(nums[i])，看第i-1个元素能不能和它相加？

为什么要减去前一个元素的值？

Answer 1

注意 table 包含 n+1 行，我们可以在更完整的代码中看到 i 索引从 1 到 n，所以nums[i-1] 指索引 0..n-1

范围内 nums[] 的从零开始的项目

   for (int i = 1; i < n+1; i++) {
        for (int j = 1; j < sum+1; j++) {
            dp[i][j] = dp[i-1][j];
            if (j >= nums[i-1]) {
                dp[i][j] = (dp[i][j] || dp[i-1][j-nums[i-1]]);
            }
        }
    }

划分相等子集和

Partition Equal Subset Sum

algorithm

dynamic-programming