波波老师关于leetcode416题的一个小疑问

Question

波波老师，您在416题中，在进行初始化的时候：

boolean[] memo = new boolean[C + 1];
        for(int i = 0 ; i <= C ; i ++)
            memo[i] = (nums[0] == i);

当i == 0的时候，您这里的判断是将其为0的时候为False （我记得java中初始化boolean数组的时候，我记得都是False）
但是随着后面的进行，我们可以看到

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

在上面代码中，如果当前背包中需要满足的capacity 刚好等于我们要填进去的值的时候，我们就需要计算
“memo[j - nums[i]]”，但是此时memo[0] = false（比如capacity == 5，但是我们刚好满足要求的item==5，运行前面的"memo[j - nums[i]" 代码不就也变成False了么？），这里会不会判断为False呢？（下图中打*部分）这里我不知道是不是这样的结果？，但是最后的结果貌似没问题，波波老师，可以帮帮我吗？是不是这里让memo[0]变为True更好呢？
第一次接触DP，真的好多都绕不明白-。-哎。。。谢谢老师哇~~~

       0      1    2     3     4     5     6     7    8    9    10     11
1      F*     T    F     F     F     F     F     F    F    F     F      F
5	  F*     T    F     F     F     F*    T     F    F    F     F      F 
11     F*     T    F     F     F     F*    T     F    F    F     F      F*
5      F*     T    F     F     F     F*    T     F    F    F     T      T*

我们 要的不应该是下面的这个结果嘛老师？

Answer 1

liuyubobobo 2020-05-17 15:25:08

赞！首先，memo[0] 设置成 true 一点儿问题都没有！对的，把 memo[0] 设置成 true，更好！

不过对于这个题目，我的写法，不设置 memo[0] 也是正确的。可以参考这里：http://coding.imooc.com/learn/questiondetail/90377.html

但是，从语义的角度，确实应该设置成 true。赞！

继续加油！：）

• 提问者 v不离不弃v #1

  老师我想明白了，但是其实还是觉得memo[0] = TRUE的话会使得解法更完美些，因为这样可以使得过程中所有的判断都是正确的，但是无论是memo[0] 为true还是false，其实最后的结果是不影响的，因memo[0]的值只会影响 memo[j - nums[i]的判断，如果填充的item仅仅为一个数字，那么在memo[0]就可以找到，如果是多个items的组合，那么过程的判断(memo[0] = false的条件下):
  1.C 的值不在最后一个未位置判断而在中间某个顺序判断：此位置判断（memo[j - nums[i]）虽然为false，但是最终memo[C]可以由其他items的组合判断为true；
  2.C的值在最后一个位置判断，此位置已经由前几个items的组合提前判断为true,无需用（memo[j - nums[i]）判断。
  
  但是个人觉得老师您的方法还是有一些瑕疵-。-（个人见解），但是在做题的时候，考虑到memo[0] = true的话对于我来说还是有些困难的，因为必须要把最终的结果图画出来才能够充分了解在写代码时候的细节考虑因素-。-
  好难哇-。-哎。

• liuyubobobo 回复 提问者 v不离不弃v #2

  你的见解完全是正确的！赞！加油！：）

Answer 2

提问者 v不离不弃v 2020-05-17 09:29:12

老师，输出的结果不应该是这样的嘛，那memo[0]是不是必须要判定为true？