老师您好,再书写完记忆化搜索的代码之后我,我想继续尝试基于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 无法得到正确的结果,是不是我在哪个细节地方理解有误。 希望老师能给出解答,万分感谢!