目标和（leetcode 494

ops/2025/4/2 5:07:17/

leetcode系列

文章目录

一、核心操作
二、外层配合操作
三、核心模式代码
总结

一、核心操作

确定dp[i][j]的含义：i为物品容量（数字），j为背包容量，dp[i][j]为用前i个物品装满容量为j的背包的方法数量
递推公式，当遍历到第i行时，如果背包容量不到nums[i]，则说明背包装不下物品i，此时dp[i][j]直接等于上一行的dp[i-1][j]；当背包容量大于等于nums[i]时，则装满背包有两种方法：不用物品i装满背包或者包括物品i装满背包，不用物品i的时候方法数量就是dp[i-1][j]，用物品i的时候方法数量就是dp[i-1][j-nums[i]]，则dp[i-1][j]等于dp[i-1][j]+dp[i-1][j-nums[i]]
初始化，首先第0行中如果背包容量大于等于物品0的容量，则只有nums[0]的那一个地方为1，其他都为0(但是dp[0][0]例外，用物品0装满容量为0的背包有一种方法，那就是不放)，但是要注意0的存在：万一物品0的容量就是0，那么装满容量为0的背包其实有两种方法，放和不放。然后第0列的初始化要看物品容量为0的个数，即为 2的物品容量为0的个数次方，这样其实就涵盖了第0个物品容量为0的情况
遍历顺序：i从1开始，j从1开始

提示：小白个人理解，如有错误敬请谅解！

二、外层配合操作

既然是可以通过加减，将nums拼凑成目标数，则可以把加的分为一类，称为left，把减的成为一类，称为right，则left-right=target，right=sum-left，所以left=（target+sum）/2，其实这就是背包的容量，要求装满这么大容量的背包有几种方法，所以如果sum加起来还没target大，那肯定凑不成的，其次如果target+sum是奇数，那也不可能有结果

三、核心模式代码

代码如下：

class Solution {
public:int findTargetSumWays(vector<int>& nums, int target) {int sum=0;for(int i=0;i<nums.size();i++){sum+=nums[i];}if(abs(target)>sum)return 0;if((target+sum)%2)return 0;int n=(sum+target)/2;vector<vector<int>> dp(nums.size(),vector<int>(n+1,0));if(nums[0]<=n) dp[0][nums[0]]=1;int count=0;for(int i=0;i<nums.size();i++){if(nums[i]==0)count++;dp[i][0]=pow(2,count);}for(int i=1;i<nums.size();i++){for(int j=1;j<=n;j++){if(j<nums[i])dp[i][j]=dp[i-1][j];else dp[i][j]=dp[i-1][j]+dp[i-1][j-nums[i]];}}return dp[nums.size()-1][n];}
};