动态规划LeetCode-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
递推公式差异：
-
最值型问题：
dp[j] = max/min(dp[j], dp[j - w] + v) -
计数型问题：
dp[j] += dp[j - w]（累加所有可能的选择）
这题依然是01背包问题，但是是01背包排列组合问题。因为每个物品（题目中的1）只用一次！这次和之前遇到的背包问题不一样了，之前都是求容量为j的背包，最多能装多少。本题则是装满有几种方法。其实这就是一个组合问题了。
这题有两个关键点，第一如何想到这题用动态规划01背包思想解决呢？第二求的背包容量是多少呢？
做这题之前我们可以先去做LeetCode-416.分割等和子集和LeetCode-1049.最后一块石头的重量Ⅱ，这几题都是01背包系列问题。
动态规划LeetCode-416.分割等和子集-CSDN博客
动态规划LeetCode-1049.最后一块石头的重量Ⅱ-CSDN博客
416和1049题我们把总和分成两个集合，把其中一个集合当作背包容量，求价值。此题题目说构造一个正负号，那我们可以分成一个正数集合一个负数集合，并求某一个集合的即可。那我们可以把dp[j]的含义表示为装满容量为j有dp[j]种方法。求出装满正数总和j有多少种方法，就是得出目标和了。那这样子我们就把它转化成了01背包问题。
那第二求的背包容量是多少呢？这里我们把正数集合为left，负数集合为right，注意我们并没有带入符号进去，只是把某些数分配到负数集合里，并没有带负号。得出以下关系：
所以所得出的整数集合总数即时我们要求的背包容量bagsize。
动规五部曲（dp含义、递推公式、初始化、遍历顺序、打印数组）
dp含义：dp[j]表示为装满容量为j有dp[j]种方法。
递推公式：
01背包排列组合问题的递推公式为：dp[j] += dp[j-nums[i]];
为什么用 +=？
对于每个数字 nums[i]，我们需要统计以下两种情况的组合数之和：
-
不选
nums[i]：组合数保持为dp[j]（不改变当前容量j的组合数）。 -
选
nums[i]：组合数增加dp[j - nums[i]]（当前容量j的组合数，加上未选nums[i]时容量为j - nums[i]的组合数）。
因此，递推公式为：
dp[j] = dp[j] + dp[j - nums[i]] # 即 dp[j] += dp[j - nums[i]]
这表示当前容量 j 的总组合数等于：
-
之前不选
nums[i]时的组合数（dp[j]），加上 -
选
nums[i]后新增的组合数（dp[j - nums[i]]）。使用
+=是因为需要累加所有可能的组合方式，而 dp[j - nums[i]] 表示未选当前数字时的组合数。
初始化：
memset(dp,0,sizeof(dp));全部初始为0，后面再重新初始dp[0]，其他下标由dp[0]推导得。
dp[0]=1 凑成和为 0 的方法数为 1（不选择任何数字）
遍历顺序：
这里是用一维滚动数组来解决，所以物品遍历的for循环放在外层，遍历背包的for循环放在内层，然后题目说物品i只能放一次，所以且内层for循环倒序遍历！
因为倒序遍历是为了保证物品i只被放入一次！。但如果一旦正序遍历了，那么物品0就会被重复加入多次！
打印数组：当遇到疑惑或者提交错误时，打印数组出来比较快速的看看哪一步有错。
以下是我在力扣c语言提交的代码，仅供参考：
一维滚动数组：
int findTargetSumWays(int* nums, int numsSize, int target) { int sum = 0; for(int i = 0;i sum，直接返回 0 if ((target + sum) % 2 != 0 || abs(target) > sum) { return 0; } int bagsize = (target + sum) / 2; int dp[bagsize+1]; // 初始化 dp 数组 memset(dp,0,sizeof(dp)); // 凑成和为 0 的方法数为 1（不选择任何数字） dp[0] = 1; for(int i = 0;i=nums[i];j--) { //01背包计数型动态规划问题一维滚动数组递推公式 dp[j] += dp[j-nums[i]]; } } return dp[bagsize];}
