LeetCode刷题【494】目标和

给你一个整数数组 nums 和一个整数 target 。

向数组中的每个整数前添加 '+' 或 '-' ，然后串联起所有整数，可以构造一个 表达式 ：

• 例如，nums = [2, 1] ，可以在 2 之前添加 '+' ，在 1 之前添加 '-' ，然后串联起来得到表达式 "+2-1" 。

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

示例 1：

输入：nums = [1,1,1,1,1], target = 3
输出：5
解释：一共有 5 种方法让最终目标和为 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
+1 + 1 + 1 + 1 - 1 = 3

示例 2：

输入：nums = [1], target = 1
输出：1

提示：

• 1 <= nums.length <= 20
• 0 <= nums[i] <= 1000
• 0 <= sum(nums[i]) <= 1000
• -1000 <= target <= 1000

直接上图，以一组数据【1,2,1,3,1】为例，浅蓝色部分为建立的DP数组的下标。

• 没有任何数字凑出结果1的方式有1种，这是一种额外的情况，以这个为基础
• 当拿到一个数字1的时候，在上一层的结果0的基础上可以加1也可以减1，那么就到达-1和1的方法就各为1种
• 当额外拿到一个数字2的时候，在原来数字1的结果-1和1的基础上，都可以进行+2和减2操作，那么此时可以得到的结果为-3、-1、1、3
• 在上一轮的结果上，继续加减1操作，如果有结果重合的部分，说明可以有不同的路径可以到达，此时结果应进行叠加
• 继续循环处理上面的操作

那么转移方程

dp[i][j] = dp[i-1][j-x]+dp[i-1][j+x]

代码，不过没有这么写，而是反向的，由第i层把值推向第i+1层

class Solution {
    public int findTargetSumWays(int[] nums, int target) {
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        if (target>sum || target < -sum){
            return 0;
        }
        int[][] dp = new int[nums.length+1][sum * 2 + 1];
        dp[0][sum] = 1;
        for (int row = 0; row < nums.length; row++) {
            for (int col = 0; col < dp[row].length; col++) {
                if (dp[row][col]!=0){
                    dp[ row + 1 ][ col - nums[row] ] += dp[row][col];
                    dp[ row + 1 ][ col + nums[row] ] += dp[row][col];
                }
            }
        }
        return dp[dp.length-1][sum + target];
    }
}