LeetCode 494.目标和 （动态规划 + 性能优化）二维数组 压缩成 一维数组
494. 目标和 - 力扣（LeetCode）
给你一个非负整数数组 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
思路整理：可以将集合分为两个集合，一个加法集合（left），一个减法集合（right）
可以求出加法集合（left），将问题转换为求出left这个集合。详细讲解看下文~
left:表示加法集合
right:表示减法集合left + right = sum
left - right = target
left = (sum + target) / 2集合{1 1 1 1 1}，分成left 和 right，生成的target如下：
left(加法集合) right(减法集合) target4 1 -33 2 12 3 -11 4 -3sum = 5
left = (sum + target) / 2
(O_O)?
发现并没有target = 2，于是当target = 2时，left = (2+5)/2 = 7/2 无法整除,
也就是 7 % 2 == 1 直接就 return 0 就好了表示找不出这样的集合能满足 left - right = target
此时问题转化为求出left这个集合，也就是说这个容器，
问在这个集合里边的所有元素装满这个容器有多少种方法？（妙啊~）有多少个元素能装满这个容器，我们就能找到符合这个题目条件的多少种
组合。此时发现这有点类似背包问题。那么left就是背包的容量，
集合{1 1 1 1 1}是物品集合
例子： nums = [1,2,1,3,1]，target = -2，当这种情况的时候，left=3
（1）二维dp数组
dp[i][j] 表示在数组 nums 的前 i 个数中选取元素，使得这些元素之和等于 j 的方案数
比如说我们要计算元素之和 等于 3 的方案数，由于
0 + 3 = 3
1 + 2 = 3
2 + 1 = 3
所以我们可以把元素之和 等于 0，1，2的方案数分别计算出来，然后再相加就可以得到元素之和等于3的方案数。
当nums[0]=1时，
- nums[0]放不进去容量为0的背包
j=0,j<nums[0],那么dp[1][0] = dp[0][0] = 1
- nums[0]放得进去容量为1、2、3的背包
j=1,j>=nums[0],那么dp[1][1] = dp[0][1] + dp[0][1-nums[0]] = 0 + dp[0][0] = 0 + 1 = 1
j=2,j>=nums[0],那么dp[1][2] = dp[0][2] + dp[0][2-nums[0]] = 0 + dp[0][1] = 0 + 0 = 0
j=3,j>=nums[0],那么dp[1][3] = dp[0][3] + dp[0][3-nums[0]] = 0 + dp[0][2] = 0 + 0 = 0
以此类推~
思考🤔
当 j < nums[i-1]时
① dp[i][j] = dp[i-1][j]; //"copy"当j >= nums[i-1]时
② dp[i][j] = dp[i-1][j] + dp[i-1][j-nums[i-1]];将①和②整合起来
dp[i][j] = dp[i-1][j];
if(j>=nums[i-1]) {dp[i][j] += dp[i-1][j-nums[i-1]];
}// 二维dp数组
class Solution {
public:int findTargetSumWays(vector<int>& nums, int target) {int sum = 0;int n = nums.size();int left = 0,right = 0;for(int i=0;i<n;i++) { sum += nums[i];}if (abs(target) > sum) return 0; // 此时没有方案if ((sum + target) % 2 == 1) return 0; // 此时没有方案left = (sum + target) / 2;vector<vector<int>> dp(n + 1, vector<int>(left + 1));dp[0][0] = 1;for (int i = 1; i <= n; i++) { // 物品for (int j = 0; j <= left; j++) { // 背包dp[i][j] = dp[i - 1][j];if (j >= nums[i-1]) {dp[i][j] += dp[i - 1][j - nums[i-1]];}}}return dp[n][left];}
};思考🤔,压缩状态，将二维dp数组 优化为 一维dp数组
将二维dp数组压缩成一维dp数组！！！ （重复利用实现滚动数组）
dp[j] += dp[j-nums[i]];dp[j] 装满容量为j的背包 有dp[j]种方法↑
dp[j-nums[i]] nums[i] dp[j-nums[i]] 1 dp[4] 凑成 dp[5]2 dp[3] 凑成 dp[5]3 dp[2] 凑成 dp[5]4 dp[1] 凑成 dp[5]5 dp[0] 凑成 dp[5]dp[5] = dp[4] + dp[3] + dp[2] + dp[1] + dp[0]也就是dp[j] += dp[j-nums[i]];初始化:dp[0] = 1
集合{0} target = 0 此时dp[0] = 1// 一维dp数组
class Solution {
public:int findTargetSumWays(vector<int>& nums, int target) {int sum = 0;int left = 0,right = 0;for(int i=0;i<nums.size();i++) { sum += nums[i];}if (abs(target) > sum) return 0; // 此时没有方案if ((sum + target) % 2 == 1) return 0; // 此时没有方案left = (sum + target) / 2;vector<int> dp(left+1,0);dp[0] = 1;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];}
};