Leetcode 494. 目标和

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

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

dp数组的含义： dp[i][j] 表示用数组中的前 i 个元素，组成和为 j 的方案数

状态转移方程：
dp[i][j] = dp[i - 1][j - nums[i]] + dp[i - 1][j+nums[i]];

可以理解为nums[i]这个元素我可以执行加，还可以执行减，那么我dp[i][j]的结果值就是加/减之后对应位置的和。

代码：

/**
 * dp[i][j + nums[i] + 1000] += dp[i - 1][j + 1000]
 * dp[i][j - nums[i] + 1000] += dp[i - 1][j + 1000]
 */
class Solution {
    public int findTargetSumWays(int[] nums, int S) {
        int sum = 0;
        int n = nums.length;
        for (int i = 0; i < n; i++)
            sum += nums[i];
        if(sum < S) return 0;
        //dp[i][j] 表示用数组中的前 i 个元素，组成和为 j 的方案数
        int[][] dp = new int[n][2 * sum + 1]; //要开辟2*sum + 1个空间 因为j存在负数的情况
        //问题的最基本解  只选择nums数组中第1个元素
        for (int i = 0; i < 2 * sum +1 ; i++) {
            dp[0][i] = 0;
        }
        // 初始化
        if (nums[0] == 0) {
            dp[0][sum] = 2; //坑，当nums[0]为0的时候，+0 ，-0均可组成0
        } else {
            dp[0][sum + nums[0]] = 1;
            dp[0][sum - nums[0]] = 1;
        }
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < 2 * sum + 1; j++) {
                // 边界
                int l = (j - nums[i]) >= 0 ? j - nums[i] : 0;
                int r = (j + nums[i]) < 2 * sum + 1 ? j + nums[i] : 0;
                dp[i][j] = dp[i - 1][l] + dp[i - 1][r];
            }
        }
        return dp[n - 1][sum + S];
    }

    public static void main(String[] args) {
        int[] nums = new int[]{0,0,0,0,0,0,0,0,1};
        System.out.println(new Solution().findTargetSumWays(nums, 1));  //256种
    }
}