494.目标和

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

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

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

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

示例 1：

1
2
3
4
5
6
7
8
输入：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：

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

01背包

有n个物品，第i个物品的体积为w[i]，价值为v[i]，每个物品至多选一个，求体积和不超过capacitys时的最大价值和

不选：在剩余容量c时，从前i-1个物品中得到的最大价值和

选：在剩余容量为c-w[i]时，从前i-1个物品中得到的最大价值和

可以很自然的写出回溯表达式：

回到这道题，表面上和01背包问题没有关系，实际上，我们假设如下：

  • 正号的数的和：p
  • 所有元素的和：s
  • 负号的数的和：s-p
  • target=正号的数-负号的数=p-(s-p)=2p-s
  • 那么p=(s+target)/2

而target和s都是已知的，问题就变成了在数组中选择元素，使之恰好装满capacity，求方案数

那么这道题的回溯表达式自然是：

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
28
29
30
31
class Solution {
    private int[] nums;  // 输入的数字数组
    private int[][] cache;  // 缓存数组，用于存储中间结果

    public int findTargetSumWays(int[] nums, int target) {
        // 计算新的目标和
        int sum = 0;
        for (int x : nums) sum += x;
        if ((sum + target) % 2 == 1 || sum < target) return 0;  // 无法实现的情况
        target = (sum + target) / 2;

        this.nums = nums;
        int n = nums.length;
        cache = new int[n][target + 1];  // 初始化缓存数组
        for (int i = 0; i < n; i++) {
            Arrays.fill(cache[i], -1);  // 将缓存数组的每个元素填充为 -1，表示未访问
        }

        return dfs(n - 1, target);  // 从数组的最后一个元素开始进行深度优先搜索
    }

    // 深度优先搜索函数
    private int dfs(int i, int c) {
        if (i < 0) return c == 0 ? 1 : 0;  // 基本条件：如果 i 小于 0，检查剩余的目标和是否为 0
        if (cache[i][c] != -1) return cache[i][c];  // 如果缓存中已有结果，直接返回
        if (c < nums[i]) return cache[i][c] = dfs(i - 1, c);  // 如果当前剩余的目标和小于 nums[i]，跳过当前元素

        return cache[i][c] = dfs(i - 1, c) + dfs(i - 1, c - nums[i]);  // 计算包含当前元素和不包含当前元素的结果
    }
}

这和198.打家劫舍的回溯代码的思路差不多，打家劫舍中用cache存储目前元素的最大值，而在本题中，用cache存储方案数的和

  • 递推

和打家劫舍一样，可以把回溯表达式改写成递推表达式

代码如下：

实际上nums[i]对应的就是f[1]开始的情况

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
28
29
30
31
32
class Solution {
    public int findTargetSumWays(int[] nums, int target) {
        // 计算调整后的目标和 target
        for (int x : nums) target += x;
        // 如果调整后的目标和为负数或奇数，返回 0，因为无法找到合法的组合
        if (target < 0 || target % 2 == 1) return 0;
        target /= 2; // 将目标和除以 2，以便后续计算

        int n = nums.length;
        // 初始化二维数组 f，用于动态规划
        int[][] f = new int[n + 1][target + 1];
        f[0][0] = 1; // 初始状态：f[0][0] = 1 表示不选择任何数时，和为 0 的情况有一种

        // 遍历每个元素
        for (int i = 0; i < n; ++i) {
            // 遍历目标和从 0 到 target
            for (int c = 0; c <= target; ++c) {
                // 如果当前目标和 c 小于当前元素 nums[i]，则不选择当前元素
                if (c < nums[i]) {
                    f[i + 1][c] = f[i][c];
                } else {
                    // 否则，可以选择当前元素或不选择当前元素
                    f[i + 1][c] = f[i][c] + f[i][c - nums[i]];
                }
            }
        }

        // 返回结果：f[n][target] 表示从前 n 个元素中选择，使和为 target 的组合数
        return f[n][target];
    }
}

  • dp

f之所以是二维数组，是因为如果用一维数组，前面的结果会影响到后面的结果，实际上，我们可以从后往前算，这样用一维数组即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public int findTargetSumWays(int[] nums, int target) {
        for (int x : nums) target += x;
        if (target < 0 || target % 2 == 1) return 0;
        target /= 2;

        int[] f = new int[target + 1];
        f[0] = 1;
        for (int x : nums)
            for (int c = target; c >= x; --c)
                f[c] += f[c - x];
        return f[target];
    }
}