494. 目标和

494. 目标和">494. 目标和

数组和sum,目标和s, 正数和x,负数和y,则x+y=sum,x-y=s,那么x=(s+sum)/2=target
0-1背包不考虑元素顺序的组合问题:选nums里的数得到target的种数,外循环nums,内循环target倒序,

确定dp数组以及下标的含义

dp[j] 表示：填满j（包括j）这么大容积的包，有dp[j]种方法
其实也可以使用二维dp数组来求解本题，dp[i][j]：使用下标为[0, i]的nums[i]能够凑满j（包括j）这么大容量的包，有dp[i][j]种方法。

确定递推公式

有哪些来源可以推出dp[j]呢？
不考虑nums[i]的情况下，填满容量为j - nums[i]的背包，有dp[j - nums[i]]种方法。
那么只要搞到nums[i]的话，凑成dp[j]就有dp[j - nums[i]] 种方法。
例如：dp[j]，j 为5，

已经有一个1（nums[i]）的话，有 dp[4]种方法凑成 dp[5]。
已经有一个2（nums[i]）的话，有 dp[3]种方法凑成 dp[5]。
已经有一个3（nums[i]）的话，有 dp[2]中方法凑成 dp[5]
已经有一个4（nums[i]）的话，有 dp[1]中方法凑成 dp[5]
已经有一个5 （nums[i]）的话，有 dp[0]中方法凑成 dp[5]

那么凑整dp[5]有多少方法呢，也就是把所有的 dp[j - nums[i]] 累加起来。
所以求组合类问题的公式，都是类似这种：

dp[j] += dp[j - nums[i]]

dp数组如何初始化

从递归公式可以看出，在初始化的时候dp[0] 一定要初始化为1，因为dp[0]是在公式中一切递推结果的起源，如果dp[0]是0的话，递归结果将都是0。
dp[0] = 1，理论上也很好解释，装满容量为0的背包，有1种方法，就是装0件物品。
dp[j]其他下标对应的数值应该初始化为0，从递归公式也可以看出，dp[j]要保证是0的初始值，才能正确的由dp[j - nums[i]]推导出来。

确定遍历顺序

01背包问题一维dp的遍历，nums放在外循环，target在内循环，且内循环倒序。

举例推导dp数组

输入：nums: [1, 1, 1, 1, 1], S: 3
bagSize = (S + sum) / 2 = (3 + 5) / 2 = 4
dp数组状态变化如下：

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int target) {
        int sum = 0;
        for(int num:nums)
            sum += num;
        if((sum+target)%2==1 || sum<abs(target))return 0;
        target = (sum+target)/2;
        vector<int> dp(target+1);
        dp[0] = 1;
        for(int num:nums)
            for(int i=target;i>=num;i--)
                dp[i] += dp[i-num];
        return dp[target];
    }
};