LeetCode494：目标和

要求

给你一个整数数组 nums 和一个整数 target 。
向数组中的每个整数前添加 ‘+’ 或 ‘-’ ，然后串联起所有整数，可以构造一个 表达式 ：

例如，nums = [2, 1] ，可以在 2 之前添加 ‘+’ ，在 1 之前添加 ‘-’ ，串联起来得到表达式 “+2-1” 。

返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。

思路

方法：动态规划
1、假设所有符号为+的元素和为x，符号为-的元素和的绝对值是y。我们想要的 target = 正数和 - 负数和 = x - y；而已知x与y的和是数组总和：x + y = sum；可以求出 x = (target + sum) / 2 = count；也就是我们要从nums数组里选出几个数，令其和为target；
2、特例判断：

如果target + sum < 0，不可能实现，返回0；
如果x不是整数，也就是target + sum不是偶数，不可能实现，返回0

3、dp[j]代表的意义：填满容量为j的背包，有dp[j]种方法。因为填满容量为0的背包有且只有一种方法，所以dp[0] = 1
4、状态转移：dp[j] = dp[j] + dp[j - num]，
当前填满容量为j的包的方法数 = 之前填满容量为j的方法数 + 之前填满容量为j - num的包的方法数
也就是当前数num的加入，可以把之前和为j - num的方法数加入进来。
5、返回dp[-1]，也就是dp[count]

public class LeetCode494 {
    public int findTargetSumWays(int[] nums, int target) {
        //数组中元素和为sum；数组元素的绝对值，和为正
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        //特例判断
        if (target + sum < 0 || (target + sum) % 2 == 1){
            return 0;
        }

        int count = (target + sum) / 2;
        int[] dp = new int[count + 1];
        dp[0] = 1;
        for (int num : nums) {
            for (int i = count; i >= num; i--) {
                dp[i] = dp[i] + dp[i-num];
            }
        }
        return dp[count];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

时间复杂度：O(n * target)
空间复杂度：O(target)