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);
    }
}

参考：

1. 目标和
2. 换一下角度，可以转换为典型的01背包问题
3. 动态规划思考全过程
4. C++ dfs和01背包
5. 背包打卡题2：0-1背包恰好装满背包的方案数
6. 494. 目标和
7. Python3 DFS 与 01背包 与 动态规划 三种方法详解
8. 动态规划击败了98%的java用户