Poison

494. Target Sum

发表于
DFS
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int findTargetSumWays(int[] nums, int target) {
        return dfs(nums, 0, 0, target);
    }

    private int dfs(int[] nums, int i, int sum, int target) {
        if (i == nums.length) {
            if (sum == target) {
                return 1;
            } else {
                return 0;
            }
        } else {
            return dfs(nums, i + 1, sum + nums[i], target) + dfs(nums, i + 1, sum - nums[i], target);
        }
    }
}
DP
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
    public int findTargetSumWays(int[] nums, int target) {
        int sum = Arrays.stream(nums).sum();
        int doubleTargetSum = sum + target;
        if (doubleTargetSum < 0 || (doubleTargetSum & 1) == 1) {
            return 0;
        }

        int targetSum = doubleTargetSum >> 1;

        // 定义 dp[i][j] 为前 i 个整数中选取一些整数可以组成和 j 的方案数
        int[][] dp = new int[nums.length + 1][targetSum + 1];
        dp[0][0] = 1;

        for (int i = 1; i <= nums.length; i++) {
            for (int j = 0; j <= targetSum; j++) {
                dp[i][j] = dp[i - 1][j];

                if (j - nums[i - 1] >= 0) {
                    dp[i][j] = dp[i - 1][j - nums[i - 1]] + dp[i - 1][j]; // 注意此处是加法而不是取 max
                }
            }
        }

        return dp[nums.length][targetSum];
    }
}
DP
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public int findTargetSumWays(int[] nums, int target) {
        int sum = Arrays.stream(nums).sum();
        int doubleTargetSum = sum + target;
        if (doubleTargetSum < 0 || (doubleTargetSum & 1) == 1) {
            return 0;
        }

        int targetSum = doubleTargetSum >> 1;

        int[] dp = new int[targetSum + 1];
        dp[0] = 1;

        for (int i = 1; i <= nums.length; i++) {
            for (int j = targetSum; j >= 0; j--) {
                if (j - nums[i - 1] >= 0) {
                    dp[j] = dp[j - nums[i - 1]] + dp[j];
                }
            }
        }

        return dp[targetSum];
    }
}
Reference

494. Target Sum