LeetCode 01背包 494. 目标和
494. 目标和
给你一个非负整数数组 nums 和一个整数 target 。
向数组中的每个整数前添加 ‘+’ 或 ‘-’ ，然后串联起所有整数，可以构造一个 表达式 ：
例如，nums = [2, 1] ，可以在 2 之前添加 ‘+’ ，在 1 之前添加 ‘-’ ，然后串联起来得到表达式 “+2-1” 。
返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。
示例 1：
输入：nums = [1,1,1,1,1], target = 3
输出：5
解释：一共有 5 种方法让最终目标和为 3 。
-1 + 1 + 1 + 1 + 1 = 3
+1 - 1 + 1 + 1 + 1 = 3
+1 + 1 - 1 + 1 + 1 = 3
+1 + 1 + 1 - 1 + 1 = 3
+1 + 1 + 1 + 1 - 1 = 3
示例 2：
输入：nums = [1], target = 1
输出：1
提示：
1 <= nums.length <= 20
0 <= nums[i] <= 1000
0 <= sum(nums[i]) <= 1000
-1000 <= target <= 1000
题解
首先对题目进行分析
所有的数字都要选，我们能做的是决定数字前面的符号，也就是这个数字是 + 还是 -
那么不妨将最后的结果视为 p - a，p为正数之和，a为负数之和，我们能够通过选择数字决定 p 是多少
又因为 p - a = target，a = sum（所有数的绝对值之和）- p，所以 p = (target + sum)/2
题目就变成从数组 nums 中选择数字使其和为 (target + sum)/2 （不能重复选择） ，这样就是01背包问题了
由于 p 是非负整数，所以如果target + sum是奇数或者负数，那么答案肯定是 0
定义 arr[ i ][ j ] 为选择前 i 个数使其和为 j 的方法数
那么对于任意 arr[ i ][ j ] ，只有选择 nums[ i-1 ] 和不选择两种可能
如果 nums[ i-1 ]>j，只能不选，arr[ i ][ j ]=arr[ i-1 ][ j ]
否则，arr[ i ][ j ]=arr[ i-1 ][ j ] + arr[ i-1 ][ j-nums[ i-1] ]
初始化 arr[0][0]=1，其余arr[0][j]为0
按顺序遍历数组即可
代码如下↓
class Solution {
public:int findTargetSumWays(vector<int>& nums, int target) {// p p是我们选择的正数// s-p s是所有正数的和// 2p-s=target// p=(target+s)/2// 那么就是选择数使其和为 p 即可int n=nums.size();int s=0;for(int i=0;i<n;i++){s+=nums[i];}if((target+s)%2 || target+s<0){return 0;}int p=(target+s)/2;vector<vector<int>> arr(n+1,vector<int>(p+1,0));arr[0][0]=1;for(int i=1;i<=n;i++){for(int j=0;j<=p;j++){arr[i][j]=arr[i-1][j];if(nums[i-1]<=j){arr[i][j]+=arr[i-1][j-nums[i-1]];}}}return arr[n][p];}
};
优化空间
二维滚动数组
我们发现 arr[ i ][ j ]=arr[ i-1 ][ j ] + arr[ i-1 ][ j-nums[ i-1] ] 或 arr[ i ][ j ]=arr[ i-1 ][ j ]
arr[ i ][ j ] 仅与上一行的 arr 有关，那我们不妨将二维数组缩减至两行，一行存 i-1 ，一行存 i
在执行过程中进行滚动，将 i 和 i-1变为 i%2 和 (i-1)%2，从而优化空间
代码如下↓
class Solution {
public:int findTargetSumWays(vector<int>& nums, int target) {// p p是我们选择的正数// s-p s是所有正数的和// 2p-s=target// p=(target+s)/2// 那么就是选择数使其和为 p 即可int n=nums.size();int s=0;for(int i=0;i<n;i++){s+=nums[i];}if((target+s)%2 || target+s<0){return 0;}int p=(target+s)/2;vector<vector<int>> arr(2,vector<int>(p+1,0));arr[0][0]=1;for(int i=1;i<=n;i++){for(int j=0;j<=p;j++){arr[i%2][j]=arr[(i-1)%2][j];if(nums[i-1]<=j){arr[i%2][j]+=arr[(i-1)%2][j-nums[i-1]];}}}return arr[n%2][p];}
};
一维数组
类似的，既然arr[ i ][ j ] 仅与上一行的 arr 有关，一行，我们能否用一位数组表示
arr[ j ] = arr[ j ] + arr[ j-nums[ i-1 ] ]（前面的arr[ j ]是arr[ i ][ j ]，后面的都是arr[ i-1 ][ j ]，上一行的）
同时，我们发现 arr[ j+1 ] 与其上一行的前面的数据有关
如果我们从前往后进行遍历，那么后面的 arr[ j+1 ] 需要的 arr[ j ] 的数据就被新计算出来的 arr[ j+1 ] 给覆盖了
所以我们需要从后向前遍历，这样就不会发生需要的数据被覆盖的问题了
代码如下↓
class Solution {
public:int findTargetSumWays(vector<int>& nums, int target) {// p p是我们选择的正数// s-p s是所有正数的和// 2p-s=target// p=(target+s)/2// 那么就是选择数使其和为 p 即可int n=nums.size();int s=0;for(int i=0;i<n;i++){s+=nums[i];}if((target+s)%2 || target+s<0){return 0;}int p=(target+s)/2;vector<int> arr(p+1);arr[0]=1;for(int i=1;i<=n;i++){for(int j=p;j>=0;j--){if(nums[i-1]<=j){arr[j]+=arr[j-nums[i-1]];}}}return arr[p];}
};