力扣：494. 目标和

力扣：494. 目标和
题目：
给你一个整数数组 nums 和一个整数 target 。
向数组中的每个整数前添加 ‘+’ 或 ‘-’ ，然后串联起所有整数，可以构造一个 表达式 ：
例如，nums = [2, 1] ，可以在 2 之前添加 ‘+’ ，在 1 之前添加 ‘-’ ，然后串联起来得到表达式 “+2-1” 。
返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。

解析：
0~n个物品放入容量为 j 的背包中其价值等于 j 的种类数 =
物品数为一个塞满背包的方法数
+物品数为两个塞满背包的方法数（且必须选定第二个物品才能是与之前不同的方法）
+物品数为三个塞满背包的方法数（且必须选定第三个物品才能是与之前不同的方法）
+物品数为n个塞满背包的方法数（其中必须选定第n个物品才能是与之前不同的方法）

此时可以看出dp[ j ]可以由前面的值表现出来，所以可以使用动态规划。

dp【j】的含义：
dp[j] 表示：填满j（包括j）这么大容积的包，有dp[j]种方法
dp数组的初始化：
dp[0] = 1，理论上也很好解释，装满容量为0的背包，有1种方法，就是装0件物品。
dp[j]其他下标对应的数值应该初始化为0，因为的物品数为0，那么装满容量为 j 的背包的方法数自然为0
确定递推公式：
由上述可知：dp[j] += dp[j - nums[i]]
确定遍历顺序：
第一个for遍历物品顺序遍历，第二个for遍历背包容量逆序遍历，其中背包容量需大于物品重量才执行循环体。
代码如下：

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int S) {
        int sum = 0;
        for (int i = 0; i < nums.size(); i++) sum += nums[i];
        if (abs(S) > sum) return 0; // 此时没有方案
        if ((S + sum) % 2 == 1) return 0; // 此时没有方案
        int bagSize = (S + sum) / 2;
	if (bagSize < 0) return 0;
        vector<int> dp(bagSize + 1, 0);
        dp[0] = 1;
        for (int i = 0; i < nums.size(); i++) {
            for (int j = bagSize; j >= nums[i]; j--) {
                dp[j] += dp[j - nums[i]];
            }
        }
        return dp[bagSize];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19