波波老师关于leetcode416题的一个小疑问
来源:9-7 面试中的0-1背包问题 Partition Equal Subset Sum
v不离不弃v
2020-05-17
波波老师,您在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*
我们 要的不应该是下面的这个结果嘛老师?
2回答
-
liuyubobobo
2020-05-17
赞!首先,memo[0] 设置成 true 一点儿问题都没有!对的,把 memo[0] 设置成 true,更好!
不过对于这个题目,我的写法,不设置 memo[0] 也是正确的。可以参考这里:http://coding.imooc.com/learn/questiondetail/90377.html
但是,从语义的角度,确实应该设置成 true。赞!
继续加油!:)
022020-05-19 -
v不离不弃v
提问者
2020-05-17
老师,输出的结果不应该是这样的嘛,那memo[0]是不是必须要判定为true?
00
相似问题
回答 1
回答 1