请稍等 ...
×

采纳答案成功!

向帮助你的同学说点啥吧!感谢那些助人为乐的人

leetcode-416不使用空间简化方法运行结果异常。

老师您好,再书写完记忆化搜索的代码之后我,我想继续尝试基于DP的解法,遇到了下面的问题:
为了熟悉背包问题的优化,我第一版的代码不使用空间优化策略,可是无法得到正确的结果,下面是代码:

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        if(nums.size()==0)
            return false;
        
        int n=nums.size();
        int sum=0;
        for(int i=0;i<nums.size();i++)
            sum+=nums[i];
        if(sum%2)
            return false;
        int C=sum/2;
        //def: memo[i][sum]:标识[0,index]范围内是否存在部分元素和==sum,true or false
        //rule: memo[i][sum] = memo[i-1][sum] || memo[i-1][sum-nums[i]]
        vector<vector<bool>> memo( n,vector<bool>(C+1,false) );
        //初始化
        for(int j=0;j<=C;j++)
            memo[0][j] = (j==nums[0]);
        for(int i=1;i<n;i++)
            for(int j=C;j>=nums[i];j--)
                memo[i][j] = ( memo[i-1][j] || memo[i-1][j-nums[i]] );
            
        return memo[n-1][C];
    }
};

而在我将辅助空间的维度变成[C+1]时,对代码进行更改,更新过后的代码如下:

public:
    bool canPartition(vector<int>& nums) {
        if(nums.size()==0)
            return false;
        
        int n=nums.size();
        int sum=0;
        for(int i=0;i<nums.size();i++)
            sum+=nums[i];
        if(sum%2)
            return false;
        int C=sum/2;
        //def: memo[i][sum]:标识[0,index]范围内是否存在部分元素和==sum,true or false
        //rule: memo[i][sum] = memo[i-1][sum] || memo[i-1][sum-nums[i]]
        //vector<vector<bool>> memo( n,vector<bool>(C+1,false) );
        vector<bool> memo(C+1,false);
        //初始化
        for(int j=0;j<=C;j++)
            memo[j] = (j==nums[0]);
        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];
    }
};

更改过后的代码可以得到正确的结果。
我不知道为什么code1 无法得到正确的结果,是不是我在哪个细节地方理解有误。 希望老师能给出解答,万分感谢!

正在回答

插入代码

1回答

你的动态规划的过程,只处理了nums[i]到C的情况,但是没有处理0到nums[i]的情况。


在0到nums[i]之间,虽然肯定无法使用第i个物品,但是依靠前面的0到i-1的物品,有可能能拼凑出来。


加上这样一句话就对了:

1
2
3
4
5
6
7
8
9
10
for(int i=1;i<n;i++){
    // 对0到nums[i]的状况,肯定不能使用nums[i],
    // 看能不能靠前面nums[0...i-1]得到
    for(int j = 0; j < nums[i]; j ++)
        memo[i][j] = memo[i - 1][j];
     
    // 下面不变
    for(int j=C;j>=nums[i];j--)
        memo[i][j] = ( memo[i-1][j] || memo[i-1][j-nums[i]] );
}


继续加油!:)

0 回复 有任何疑惑可以回复我~
  • 提问者 怀瑜 #1
    非常感谢!
    回复 有任何疑惑可以回复我~ 2019-07-08 17:05:52
  • 提问者 怀瑜 #2
    感谢老师。对于产生这种问题我的理解是:
    使用空间复杂的为o(c+1)的算法时,考虑第i次循环,memo[j-nums[i]]存储 其实就是在第i-1次循环所得到的结果。而使用空间复杂的为o(n*(c+1))的算法时,由于memo[i-1][j-nums[i]]初始化为false,而代码里面没有对j<nums[i]的情况进行计算,导致错误。因为对于j<nums[i]的情况来说,此时第i个元素无法被放进去,因此memo[i-1][j]=memo[i][j]。优化后的算法由于对空间的重复利用,所以这个问题不会发生。而优化前则必须要考虑这种问题。
    回复 有任何疑惑可以回复我~ 2019-07-08 17:13:32
  • liuyubobobo 回复 提问者 怀瑜 #3
    赞:)非常正确。继续加油!:)
    回复 有任何疑惑可以回复我~ 2019-07-09 00:17:21
问题已解决,确定采纳
还有疑问,暂不采纳
意见反馈 帮助中心 APP下载
官方微信