题目：目标和

给定一个非负整数数组，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位整数存下。

来源：力扣（LeetCode）第494题

链接：https://leetcode-cn.com/problems/target-sum

分析：

这是一道动态规划题，也可以使用dfs完成。
此外，还有一种使用数学方法来简化的dp。
常规dp很简单，第一个状态是当前为第几个，第二个状态为当前的和是多少。
我们有两种选择，第一种是当前为+号，那么用当前的和减去当前的值去找上一次的和。
如果当前是-号，就用当前的和加上当前的值去找上一次的和。
然后来看看数学方法简化dp。
设x为其中一个解的正数和，y为其中一个解的负数和的绝对值。
因此我们可以得到两个公式
x + y = sum(sum是整个数组的和)
x - y = S(S是目标值)
上下一相加，得x = (sum + S) / 2
因此我们只要知道x有多少种可能就行了
所以问题转化为01背包问题，找到当长度为数组长度时，x有多少种可能。状态直接转为一维。
x也就是符号为正的情况。

代码：

先放上常规dp

class Solution {
public int findTargetSumWays(int[] nums, int S) {
    if (S < 0) S = -S;
    int sum = 0;
    for (int num : nums) sum += num;
    if (sum < S) return 0;
    int len = nums.length, en = 2 * sum + 50, st = en / 2;
    int[][] dp = new int[len][en+1];
    dp[0][st+nums[0]] += 1;dp[0][st-nums[0]] += 1;
    for (int i = 1; i < len; i++) {
        for (int j = 0; j <= en; j++) {
            if (j - nums[i] >= 0)
                dp[i][j] += dp[i-1][j-nums[i]];
            if (j + nums[i] <= en)
                dp[i][j] += dp[i-1][j+nums[i]];
        }
    }
    return dp[len-1][st+S];
}
}

顺便放上dfs+记忆化和不加记忆化

class Solution {
private int len, S;
public int findTargetSumWays(int[] nums, int S) {
    this.len = nums.length;
    this.S = S;
    return dfs(nums, 0, 0);
}

public int dfs(int[] nums, int curlen, int cursum) {
    int ans = 0;
    if (cursum == S && curlen == len) return 1;
    if (curlen >= len) return 0;
    ans = dfs(nums, curlen + 1, cursum + nums[curlen]) + dfs(nums, curlen + 1, cursum - nums[curlen]);
    return ans;
}
}

class Solution {
private int len, S, st;
public int findTargetSumWays(int[] nums, int S) {
    this.len = nums.length;
    this.S = S;
    int sum = 0;
    for (int num : nums) sum += num;
    int[][] memo = new int[len][2000];
    st = 1000;
    return dfs(nums, 0, 0, memo);
}

public int dfs(int[] nums, int curlen, int cursum, int[][] memo) {
    int ans = 0;
    if (cursum == S && curlen == len) return 1;
    if (curlen >= len) return 0;
    if (memo[curlen][st+cursum] != 0) return memo[curlen][st+cursum];
    ans = dfs(nums, curlen + 1, cursum + nums[curlen], memo) + dfs(nums, curlen + 1, cursum - nums[curlen], memo);
    memo[curlen][st+cursum] = ans;
    return ans;
}
}

最后放上数学+dp

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

两个dp的速度很快，一维dp最快，记忆化+dfs慢了许多。