动态规划

题目-目标和

给定一个非负整数数组，a1, a2, …, an, 和一个目标数，S。现在你有两个符号 + 和 -。对于数组中的任意一个整数，你都可以从 + 或 -中选择一个符号添加在前面。

返回可以使最终数组和为目标数 S 的所有添加符号的方法数。

示例1

  • 输入：nums: [1, 1, 1, 1, 1], S: 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

《代码随想录》算法公开课
力扣题目链接

思路

本题要如何使表达式结果为target，

既然为target，那么就一定有 left组合 - right组合 = target。

left + right = sum，而sum是固定的。right = sum - left

left - (sum - left) = target 推导出 left = (target + sum)/2

target是固定的，sum是固定的，left就可以求出来。

此时问题就是在集合nums中找出和为left的组合。

动态规划五步曲

假设加法的总和为x，那么减法对应的总和就是sum - x。所以我们要求的是 x - (sum - x) = target，而x = (target + sum) / 2

此时问题就转化为，用nums装满容量为x的背包，有几种方法

注意：这里的x，就是bagSize，也就是我们后面要求的背包容量

  1. 确定dp数组以及下标的含义

先用二维dp数组求解本题，dp[i][j]：使用下标为[0, i]的nums[i]能够凑满j（包括j）这么大容量的包，有dp[i][j]种方法。

  1. 确定递推公式

我们先手动推导一下，这个二维数组里面的数值

  • 先只考虑物品0，如下图：

装满背包容量为0的方法个数是1，即 放0件物品。
装满背包容量为1的方法个数是1，即 放物品0。
装满背包容量为2 的方法个数是0，目前没有办法能装满容量为2的背包。

  • 接下来 考虑 物品0 和 物品1，如下图：

装满背包容量为0的方法个数是1，即 放0件物品。
装满背包容量为1的方法个数是2，即 放物品0或者放物品1。
装满背包容量为2的方法个数是1，即 放物品0和放物品1。
其他容量都不能装满，所以方法是0。

  • 接下来 考虑 物品0、物品1和物品2，如下图：

装满背包容量为0的方法个数是1，即放0件物品。
装满背包容量为1的方法个数是3，即放物品0或者放物品1 或者 放物品2。
装满背包容量为2的方法个数是3，即放物品0和放物品1、放物品0和物品2、放物品1和物品2。
装满背包容量为3的方法个数是1，即 放物品0和物品1和物品2。
494-1

现在我们来看看dp[2][2]由什么方向推出来！

dp[2][2] = 3，即 放物品0 和 放物品1、放物品0 和 物品 2、放物品1 和 物品2

  • 容量为2 的背包，如果不放 物品2 有几种方法呢？

有dp[1][2]种方法，即 背包容量为2，只考虑物品0 和 物品1 ，有 dp[1][2] 种方法

  • 容量为2 的背包， 如果放 物品2 有几种方法呢？

首先 要在背包里 先把物品2的容量空出来， 装满刨除物品2容量 的背包 有几种方法呢？刨除物品2容量后的背包容量为 1

此时装满背包容量为1 有dp[1][1]种方法，即： 不放物品2，背包容量为1，只考虑物品 0 和 物品 1，有 dp[1][1] 种方法

即：dp[2][2] = 容量为2的背包不放物品2有几种方法 + 容量为2的背包放物品2有几种方法

  • 所以 dp[2][2] = dp[1][2] + dp[1][1]

上述过程可抽象为如下：

  • 不放物品i：即背包容量为j，里面不放物品i，装满有dp[i - 1][j]中方法。

  • 放物品i： 即：先空出物品i的容量，背包容量为（j - 物品i容量），放满背包有 dp[i - 1][j - 物品i容量] 种方法。

本题中，物品i的容量是nums[i]，价值也是nums[i]

即：递推公式：dp[i][j] = dp[i - 1][j] + dp[i - 1][j - nums[i]]

观察递推公式可知，我们会存在放不下i物品的情况，当j-nums[i]小于0时，说明背包容量装不下物品i，所以此时装满背包的方法值 等于不放物品i的装满背包的方法，即：dp[i][j] = dp[i - 1][j]

  1. dp数组如何初始化

先明确递推的方向，求解 dp[2][2] 是由上方和左上方推出。那么二维数组的最上行 和 最左列一定要初始化，这是递推公式推导的基础。

  • 最上行：
    dp[0][j]：只放物品0， 把容量为j的背包填满有几种方法。只有背包容量为 物品0 的容量的时候，方法为1，正好装满。其他情况下，要不是装不满，要不是装不下。
    所以初始化：dp[0][nums[0]] = 1 ，其他均为0 。

  • 最左列：
    dp[i][0] : 背包容量为0， 放物品0 到 物品i，装满有几种方法。都是有一种方法，就是放0件物品。
    即 dp[i][0] = 1

  1. 确定遍历顺序

在明确递推方向时，我们知道 当前值 是由上方和左上方推出。那么我们的遍历顺序一定是 从上到下，从左到右。因为只有这样，我们才能基于之前的数值做推导。

  1. 举例推导dp数组

自己推，结果如图：
494-2

代码实现-二维数组

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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
class Solution {
    public int findTargetSumWays(int[] nums, int target) {
        int sum = 0;

        //对数组进行求和
        for(int i : nums){
            sum += i;
        }

        //当目标和大于数组和时，表示没有组合方法可以实现目标和，即返回0种方法
        if(Math.abs(target) > sum || (target + sum) % 2 != 0)return 0;

        //根据上述分析，求出背包的最大容量，x的分析上述已给出
        int x = (target+sum) / 2;

        //dp[i][j] 下标0-i的nums元素填满大小为j的背包的方法数
        int[][] dp = new int[nums.length][x+1];

        //对dp数组进行初始化
        if(nums[0] <= x)dp[0][nums[0]] = 1;

        int numZeros = 0;
        for(int i = 0; i < nums.length; i++) {
            if(nums[i] == 0) {
                numZeros++;
            }
            dp[i][0] = (int) Math.pow(2, numZeros);

        }

        for(int i = 1; i < nums.length; i++){
            for(int j = 1; j <= x; j++){
                //当前物品i无法放入j大小的背包
                if(j < nums[i]) dp[i][j] = dp[i-1][j];
                else{
                    //当前物品i能放进j大小的背包
                    //不放nums[i]和放nums[i]
                    dp[i][j] = dp[i-1][j] + dp[i-1][j-nums[i]];
                }
            }
        }

        return dp[nums.length-1][x];
        
    }
}

代码实现-一维数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public int findTargetSumWays(int[] nums, int target) {
        int sum = 0;
        for (int i = 0; i < nums.length; i++) sum += nums[i];

        //如果target的绝对值大于sum，那么是没有方案的
        if (Math.abs(target) > sum) return 0;
        //如果(target+sum)除以2的余数不为0，也是没有方案的
        if ((target + sum) % 2 == 1) return 0;

        int bagSize = (target + sum) / 2;
        int[] dp = new int[bagSize + 1];
        dp[0] = 1;

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

        return dp[bagSize];
    }
}