题目描述
分析
01背包的题做起来最难的是把原问题转化成01背包题,通常需要写出题目中所有的数学关系,对公式进行化简后得到01背包的类型。
在这种情景下还需要重新定义dp数组的含义
于是连带的。dp数组的递推公式也要重新想
大胆的按照五步骤结合题目分析的话其实并不是难到无迹可寻,而如果太死板的套用模版的话反而可能会把问题复杂化。
于是得到代码如下:
class Solution {
public:
int findTargetSumWays(vector<int>& nums, int target) {
if(nums.size() == 1){
if(abs(nums[0]) == abs(target)){
return 1;
}else{
return 0;
}
}
int sum = accumulate(nums.begin(), nums.end(), 0);
// if(sum < target){
// return 0;
// }
// if(sum == target){
// return 1;
// }
if((target + sum)%2 == 1){
return 0;
}
if(abs(target) > abs(sum)){
//这里排除了target + sum为负的情况,当出现这种情况时方案数为0
return 0;
}
int length = (target + sum)/2;
//cout<<length<<endl;
vector<int> dp(length+1,0);
dp[0] = 1;
for(int i = 0; i < nums.size();i ++){
for(int j = length; j >= nums[i]; j--){
dp[j] += dp[j - nums[i]];
}
// for(int k = 0; k < length+1; k++){
// cout<<dp[k]<<" ";
// }
// cout<<endl;
}
return dp[length];
}
};
就算清楚思路之后,这题在细节上也很难把握,因为数组和target都有负数的出现。
标签:01,return,target,nums,int,sum,力扣,背包,dp From: https://www.cnblogs.com/satsuki26681534/p/18075140