494. 目标和【动态规划】

1、题目描述

2、示例

3、分析

目标是求 n 种解，题目中的示例给的太过简单。
按照传统的思路（回溯法）运用循环可以解决，但是时间复杂度是 2 的 n 次方，肯定是行不通的。
（1）可以先尝试计算数组的总和，用于比较，如果总和大于 targer ，则结果为 0 。
（2）如果总和 - nums[n] * 2 小于targer，则 nums[n] 前的符号必然为 “+”。
（3）既然是动态规划问题，时间复杂度必然不高，

4、代码

class Solution {
    public int findTargetSumWays(int[] nums, int target) {
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        int diff = sum - target;
        if (diff < 0 || diff % 2 != 0) {
            return 0;
        }
        int neg = diff / 2;
        int[] dp = new int[neg + 1];
        dp[0] = 1;
        for (int num : nums) {
            for (int j = neg; j >= num; j--) {
                dp[j] += dp[j - num];
            }
        }
        return dp[neg];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

5、结果

整个思路是没有问题的 但是动态规划和 0 - 1背包还掌握的不好 需要在理解一下