494. 目标和

题目：

494. 目标和
在这里插入图片描述

题解：

1. 题解一：DFS枚举

在这里插入图片描述

2. 题解二：动态规划（首选）

在这里插入图片描述

代码：

1. 代码一：DFS枚举

public class code494 { 
    // 方法一: DFS枚举
    public int count = 0;
    public int findTargetSumWays(int[] nums, int S)
    { 
        dfs(nums, S, 0, 0);
        return count;
    }
    public void dfs(int nums[], int S, int i, int sum)
    { 
        if(i == nums.length && sum == S)
        { 
            count++;
            return;
        }
        if(i == nums.length)
        { 
            return;
        }
        dfs(nums, S, i + 1, sum + nums[i]);
        dfs(nums, S, i + 1, sum - nums[i]);
    }
    public static void main(String[] args) { 
        int nums[] = {  1, 1, 1, 1, 1 };
        int S = 3;
        code494 test = new code494();
        int res = test.findTargetSumWays(nums, S);
        System.out.println(res);
    }
}

2. 代码二：动态规划（首选）

public class code494 { 
    // 方法二: 动态规划
    public int findTargetSumWays(int[] nums, int S) { 
        int sum = 0;
        for(int i = 0; i < nums.length; i++)
        { 
            sum = sum + nums[i];
        }
        // 绝对值范围超过了sum的绝对值范围则无法得到
        if(Math.abs(S) > Math.abs(sum))
        { 
            return 0;
        }
        int len = nums.length;
        // - 0 +
        int target = sum * 2 + 1;
        // dp[i][j]: 从数组 nums 中 0 —— i 的元素(前 i 个元素)进行加减，可以得到 j 的方法数量。
        int dp[][] = new int[len][target];
        // 初始化
        if(nums[0] == 0)
        { 
            dp[0][sum] = 2; // 如果 nums[0] == 0 那么 dp[0][sum] 需要初始化为2，因为加减 0 都得0。
        }
        // 初始化表格的第一行，sum表示的是表格中【0】所在的那一列的下标；
        // 而对 nums[0] 执行加减呢，是因为当前 nums[0] 这个数可以执行一次加，也可以执行一次减；
        // 而为什么赋值为 1 呢，是因为当前这个 nums[0] 能够得到对应的值的情况只有一种。
        else
        { 
            dp[0][sum + nums[0]] = 1;
            dp[0][sum - nums[0]] = 1;
        }
        for(int i = 1; i < len; i++)
        { 
            for(int j = 0; j < target; j++)
            { 
                // 边界处理
                int left = (j - nums[i]) >= 0 ? j - nums[i]: 0;
                int right = (j + nums[i]) < target ? j + nums[i]: 0;
                // nums[i] 这个元素我可以执行加，还可以执行减，那么 dp[i][j] 的结果值就是加/减之后对应位置的和。
                dp[i][j] = dp[i - 1][left] + dp[i - 1][right];
            }
        }
        return dp[len - 1][sum + S];
    }
    public static void main(String[] args) { 
        int nums[] = {  1, 1, 1, 1, 1 };
        int S = 3;
        code494 test = new code494();
        int res = test.findTargetSumWays(nums, S);
        System.out.println(res);
    }
}