Partion Equal Subset Sum ? 授课代码有点儿小问题

Question

老师，你的代码有点儿问题，下面的memo[0] 应该初始化为true?
class Solution {

public:
bool canPartition(vector& nums) {

    int sum = 0;
    for(int i = 0 ; i < nums.size() ; i ++){
        assert(nums[i] > 0);
        sum += nums[i];
    }

    if(sum % 2)
        return false;

    int n = nums.size();
    int C = sum / 2;
    vector<bool> memo(C + 1, false);
    for(int i = 0 ; i <= C ; i ++)
        memo[i] = (nums[0] == i);

    for(int i = 1 ; i < n ; i ++)
        for(int j = C; j >= nums[i] ; j --)
            memo[j] = memo[j] || memo[j - nums[i]];

    return memo[C];
}

};

Answer 1

liuyubobobo 2018-11-27 19:56:24

赞！

从memo的语义来讲，应该初始化为true。

不过，在这个问题中，由于有限定条件，nums中的所有元素一定为正，且nums非空。所以C = 0一定不是原问题的解。所以说memo[0]=false也ok：）

实际上，由于这个限制，在这个递推过程中，memo[0]的值根本不会影响结果。因为在递推过程中，访问memo[0]的时候，只有可能是j - nums[i] == 0的情况，而此时，memo[j]一定为true（因为memo初始化的方式）。所以memo[0]是多少不会影响||逻辑的结果：）

不信试一试，显示地将memo[0]初始化为true或者false，程序都是正确的：）

继续加油！

• MarcoLiLiLi #1

  波波老师， 您说“访问memo[0]的时候，只有可能是j - nums[i] == 0的情况，而此时，memo[j]一定为true（因为memo初始化的方式）”， 我用[1,5,11,5]这个例子推到那个过程的时候发现当 i = 2（num[2]=11）, 最里层 j = 11, memo[j - num[2]] = false (因为memo[0]初始化就是false)。 但容量为11的背包确实可以放下11这个物品呀，不知道是不是我哪里理解的不对？总觉得memo[0]如果不设置为true的话就会出现这种刚好满足背包容量的物品被程序“认定”为不满足。

• liuyubobobo 回复 MarcoLiLiLi #2

  在上面的代码中，如果没有 for(int i = 0 ; i <= C ; i ++) memo[i] = (nums[0] == i); 这个初始条件的话，memo[0] 不设成 true，程序就是错误的。但是，一旦有了这个初始化，在题目的限制条件下，是正确的。因为，如果这个和只由一个数字填充，在这个初始化的时候，肯定找到了；但如果有多个数字填充，那么 nums[0] 一定发挥了作用，那么在访问到 j - nums[i] == 0 的时候，这个 j 肯定也已经使用其他数字的和组成了。用你的这个测试用例，运行一下上面的代码，试试看？不过，确实，初始使用 memo[0] = true 的方式更好。我有时间补充一下相关的讲解。谢谢建议！：）