目标和
学习记录自代码随想录
要点:1.想到±代表其实求的是连个组合的差值,进而记left为正组合,right为负组合,则有
{ l e f t − r i g h t = t a r g e t l e f t + r i g h t = s u m \left \{ \begin{matrix} left-right=target \\ left+right=sum \end{matrix} \right . {left−right=targetleft+right=sum,从而可以推导出 l e f t = s u m + t a r g e t 2 left = \frac{sum+target}{2} left=2sum+target;
2.想到以上面所求left为背包容量,得到dp[j]含义为装满背包容量j的组合方法数目;
3.求组和数目的递推公式一般为 d p [ j ] + = d p [ j − n u m s [ i ] ] dp[j] += dp[j-nums[i]] dp[j]+=dp[j−nums[i]]
4.dp数组初始化时dp[0]为1,其余为0否则递推公式会无效
class Solution {
public:
int findTargetSumWays(vector<int>& nums, int target) {
// 1.一加一减两种方法实际上是将数组分为两个集合left(+),right(-)
// 则有left-right = target, 且left+right = sum, 则推出left = (sum+target)/2
int sum = 0;
for(int a : nums) sum += a;
if(sum + target < 0) return 0; // 总和小于target则无法实现结果
if((sum + target) % 2) return 0;
int left = (sum + target) / 2;
// dp[j]代表背包容量为j时填满背包有dp[j]种方法
vector<int> dp(1001, 0);
// 2.递推公式(求组和有多少种方法一般可参考此递推公式):dp[j] += dp[j-nums[i]](对所有小于等于j的nums[i]求和)
// 3.初始化dp数组为dp[0] = 1, 其余为0
dp[0] = 1; // 若dp[0]为0则所有递推结果均为0
// 4.遍历顺序先遍历物品,再反向遍历容量
for(int i = 0; i < nums.size(); i++){
for(int j = left; j >= nums[i]; j--){
dp[j] += dp[j-nums[i]];
}
}
return dp[left];
}
};