波波老师关于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。赞!


继续加油!:)

0
2
liuyubobobo
回复
v不离不弃v
你的见解完全是正确的!赞!加油!:)
2020-05-19
共2条回复

v不离不弃v

提问者

2020-05-17

//img.mukewang.com/szimg/5ec093400988f7b214510452.jpg

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

0
0

玩转算法面试-- Leetcode真题分门别类讲解

课程配套大量BAT面试真题,高频算法题解析,强化训练

7410 学习 · 1150 问题

查看课程