leetcode494 目标和 关于动态规划思想的解释（小白版

给定一个非负整数数组，a1, a2, …, an, 和一个目标数，S。现在你有两个符号 + 和 -。对于数组中的任意一个整数，你都可以从 + 或 -中选择一个符号添加在前面。

返回可以使最终数组和为目标数 S 的所有添加符号的方法数。

示例 1:

输入: nums: [1, 1, 1, 1, 1], S: 3 输出: 5 解释:

-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

一共有5种方法让最终目标和为3。

注意:

数组的长度不会超过20，并且数组中的值全为正数。 初始的数组的和不会超过1000。 保证返回的最终结果为32位整数。

class Solution {
          
   
    public int findTargetSumWays(int[] nums, int S) {
          
   
        //原问题等同于：找到nums一个正子集和一个负子集，使得总和等于target。
        //找到nums的一个子集P，使得sum(P) = (target + sum(nums))/2
        int sum = 0;
        for(int num : nums)
            sum += num;
        if(sum < S || (S + sum) % 2 != 0)
            return 0;
        return subsetSum(nums, (S + sum) / 2);
    }
    public int subsetSum(int[] nums, int s){
          
     //以s这个数为和的子集有多少个
        int[] dp= new int[s + 1];
        dp[0] = 1;  //以0为和的子集有一个，是空集
        for(int num : nums)
            for(int i = s; i >= num; i--)
                dp[i] += dp[i - num]; 			//核心代码
        return dp[s];
    }
}
// sum(P) - sum(N) = target
// sum(P) + sum(N) + sum(P) - sum(N) = target + sum(P) + sum(N)
//                        2 * sum(P) = target + sum(nums)

提取这段代码单独讨论

dp[i] += dp[i - num]; 			//核心代码

以 1，2，1，3 S -> 4 为例

1. 目标和的问题首先被转化为找到目标和为4的子集的个数
2. 核心思想是不断通过之前迭过的数据进行后续处理
3. dp数组大小设置为[s+1]是为了将0作为只由目标值自身组成的唯一一种情况
4. 执行顺序：i = 4，num = 1时，便需执行4次，因为4的组成至多是由四个1组成
5. i = 4，num = 2时，便需执行3次，因为4 - 2 = 2，剩余的2，至多由两个1组成
6. 以此类推实际上 0 1 2 3 4 中每个索引对应的子集个数，均被保存在该索引下，比他大的数将直接使用前面计算过的值，进行迭代

再附上递归算法

class Solution {
          
   
    int res = 0;
    public int findTargetSumWays(int[] nums, int S) {
          
   
        helper(nums, S, 0);  //递归
        return res;
    }
    public void helper(int[] nums, int S, int p){
          
   
        if(p >= nums.length)
        {
          
   
            if(S == 0) res++;
            return ;
        }
        helper(nums, S - nums[p], p + 1);
        helper(nums, S + nums[p], p + 1);
    }
}