leetcode|LeetCode第 494 题（目标和(C++)）动态规划|leetcode

494. 目标和 - 力扣（LeetCode）
注意几个点：

数组是非负的
一个元素只能用一次
每个元素都是必选的（要么+要么-）
符号+ / -号的顺序是需要考虑的
初始的数组的和不会超过 1000

其实一开始容易想到这个状态：
dp[i][j]表示前i个元素能够凑成和值j的方法数：
d p [ i ] [ j ] = d p [ i ? 1 ] [ j ? n u m s [ i ? 1 ] ] + d p [ i ? 1 ] [ j + n u m s [ i ? 1 ] ] dp[i][j] = dp[i-1][ j-nums[i-1]] + dp[i-1][j+nums[i-1]] dp[i][j]=dp[i?1][j?nums[i?1]]+dp[i?1][j+nums[i?1]]
因为这题元素只能选一次，只有两种选择（+/-），所以状态转移还是比较单一的，但是写代码的时候就出现问题了，因为和值为负数的情况没有考虑到。比如例子中实际上dp[2][0] = 2，因为前两个元素凑成和值0有两种选择：(+1, -1), (-1, +1)，但是上面的转移方程考虑不到负数的情况，所以会出错。
所以负数的情况需要考虑，而数组的下标又不能为负，所以可以采取数组下标统一加上一个偏置的方法，避免下标为负的情况。
所以原本错误的代码是这样的(01背包套模板即可)：

class Solution { public: int findTargetSumWays(vector& nums, int S) { if(S > 1000 || S < -1000)return 0; int n = nums.size(); //dp[i][j]表示前i个元素能够凑成和值j的方法数 vector> dp(n+1, vector(S+1, 0)); dp[0][0] = 1; //前0个元素组成和值10的方法数为1 for(int i = 1; i <= n; ++i){//考虑前i个物品 for(int j = 0; j <= S; ++j){//能够组成的和值-1000 ~ 1000 //两个if条件是为了保证下标不越界 if(j - nums[i-1] >= 0) dp[i][j] += dp[i-1][j - nums[i-1]]; if(j + nums[i-1] <= S) dp[i][j] += dp[i-1][j + nums[i-1]]; } } return dp[n][S]; } };

加上偏置之后，就变成这样：

class Solution { public: int findTargetSumWays(vector& nums, int S) { if(S > 1000 || S < -1000)return 0; int n = nums.size(); //dp[i][j]表示前i个元素能够凑成和值j-1000的方法数 vector> dp(n+1, vector(2001, 0)); dp[0][1000] = 1; //前0个元素组成和值1000-1000=0的方法数为1 for(int i = 1; i <= n; ++i){//考虑前i个物品 for(int j = -1000; j <= 1000; ++j){//能够组成的和值-1000 ~ 1000 //和值-1000 ~ 1000映射到数组中对应下标是0 ~ 2001 //两个if条件是为了保证下标不越界 if(j - nums[i-1] >= -1000) dp[i][j+1000] = dp[i-1][j+1000 - nums[i-1]]; if(j + nums[i-1] <= 1000) dp[i][j+1000] += dp[i-1][j+1000 + nums[i-1]]; } } return dp[n][S+1000]; } };

那么其实也不用非要那么大的数组，最大的偏置最多就是数组的全部和值：

class Solution { public: int findTargetSumWays(vector& nums, int S) { int sum = accumulate(nums.begin(), nums.end(), 0); if(S > 1000 || S < -1000 || S > sum)return 0; int n = nums.size(); //dp[i][j]表示前i个元素能够凑成和值j-sum的方法数 vector> dp(n+1, vector(2*sum+1, 0)); dp[0][sum] = 1; //前0个元素组成和值sum-sum=0的方法数为1 for(int i = 1; i <= n; ++i){//考虑前i个物品 for(int j = -sum; j <= sum; ++j){//能够组成的和值-sum ~ sum //和值-sum ~ sum映射到数组中对应下标是0 ~ 2*sum+1 //两个if条件是为了保证下标不越界 if(j - nums[i-1] >= -sum) dp[i][j+sum] = dp[i-1][j+sum - nums[i-1]]; if(j + nums[i-1] <= sum) dp[i][j+sum] += dp[i-1][j+sum + nums[i-1]]; } } return dp[n][S+sum]; } };

观察一下可以进行状态压缩，使用滚动数组即可，因为每一行只与前一行有关。

class Solution { public: int findTargetSumWays(vector& nums, int S) { int sum = accumulate(nums.begin(), nums.end(), 0); if(S > 1000 || S < -1000 || S > sum)return 0; int n = nums.size(); //dp[i][j]表示前i个元素能够凑成和值j-sum的方法数 vector> dp(2, vector(2*sum+1, 0)); dp[0][sum] = 1; //前0个元素组成和值sum-sum=0的方法数为1 int cur = 0; for(int i = 1; i <= n; ++i){//考虑前i个物品 cur = i%2; for(int j = -sum; j <= sum; ++j){//能够组成的和值-sum ~ sum //和值-sum ~ sum映射到数组中对应下标是0 ~ 2*sum+1 //两个if条件是为了保证下标不越界 if(j - nums[i-1] >= -sum) dp[cur][j+sum] = dp[1-cur][j+sum - nums[i-1]]; if(j + nums[i-1] <= sum) dp[cur][j+sum] += dp[1-cur][j+sum + nums[i-1]]; } } return dp[n%2][S+sum]; } };

最后，总感觉这个题可以进行转换，像是LeetCode第 416 题：分割等和子集(C++)_zj-CSDN博客那样可以转为0-1背包问题，但是又没想到怎么转，知道看了这个题解：
换一下角度，可以转换为典型的01背包问题 - 目标和 - 力扣（LeetCode）
原理其实就是挑选一部分元素作为正数，剩下的作为负数，两部分相差即为S，既然S已知，那知道正数的那一部分，负数的那一部分自然也就知道了。所有我们只需要计算正数的那一部分就可以了。
而对于01背包问题来说，元素就不是必选的了，可选可不选

class Solution { public: int findTargetSumWays(vector& nums, int S) { int sum = accumulate(nums.begin(), nums.end(), 0); if(S > 1000 || S < -1000 || S > sum)return 0; if((S + sum)%2) return 0; //为奇数的话，下面就算不出有效的背包容量 int cap = (S + sum)/2; //正数的背包容量 int n = nums.size(); //dp[i][j]表示前i个元素能够凑成和值j的方法数 vector> dp(n+1, vector(cap+1, 0)); dp[0][0] = 1; //前0个元素组成和值0的方法数为1 for(int i = 1; i <= n; ++i){//考虑前i个物品 for(int j = 0; j <= cap; ++j){ //if条件是为了保证下标不越界 //元素可以选或者不选 if(j - nums[i-1] >= 0) dp[i][j] = dp[i-1][j - nums[i-1]] + dp[i-1][j]; else dp[i][j] = dp[i-1][j]; //只能继承之前的值 } } return dp[n][cap]; } };

【leetcode|LeetCode第 494 题（目标和(C++)）】也可以进行状态压缩，注意后向前遍历避免值覆盖就行。