动态规划

1. 0-1背包问题

通用解题步骤

  • 确定dp数组（dp table）以及下标的含义
  • 确定递推公式
  • dp数组如何初始化
  • 确定遍历顺序
  • 举例推导dp数组

有n件物品和一个最多能背重量为w 的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大。

背包最大重量为4。

物品为：

重量 价值
物品0 1 15
物品1 3 20
物品2 4 30

问背包能背的物品最大价值是多少？

依然动规五部曲分析一波。

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

对于背包问题，可以使用二维数组，即dp[i][j]表示从下标为[0-i]的物品里任意取，放进容量为j的背包，价值总和最大是多少。

  1. 确定递推公式

再回顾一下dp[i][j]的含义：从下标为[0-i]的物品里任意取，放进容量为j的背包，价值总和最大是多少。

那么可以有两个方向推出来dp[i][j]，

  • 不放物品i：由dp[i - 1][j]推出，即背包容量为j，里面不放物品i的最大价值，此时dp[i][j]就是dp[i - 1][j]。(其实就是当物品i的重量大于背包j的重量时，物品i无法放进背包中，所以被背包内的价值依然和前面相同。)
  • 放物品i：由dp[i - 1][j - weight[i]]推出，dp[i - 1][j - weight[i]]为背包容量为j - weight[i]的时候不放物品i的最大价值，那么dp[i - 1][j - weight[i]] + value[i] （物品i的价值），就是背包放物品i得到的最大价值

所以递归公式： dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);

  1. dp数组如何初始化

首先从dp[i][j]的定义出发，如果背包容量j为0的话，即dp[i][0]，无论是选取哪些物品，背包价值总和一定为0。

状态转移方程dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);可以看出i是由i-1 推导出来，那么i为0的时候就一定要初始化。

dp[0][j]，即：i为0，存放编号0的物品的时候，各个容量的背包所能存放的最大价值。

那么很明显当 j < weight[0]的时候，dp[0][j]应该是 0，因为背包容量比编号0的物品重量还小。

当j >= weight[0]时，dp[0][j]应该是value[0]，因为背包容量放足够放编号0物品。

代码初始化如下：

1
2
3
4
// 正序遍历
for (int j = weight[0]; j <= bagweight; j++) {
    dp[0][j] = value[0];
}

此时dp数组初始化情况如图所示：

动态规划-背包问题7

  1. 确定遍历顺序

那么问题来了，先遍历 物品还是先遍历背包重量呢？

其实都可以！！ 但是先遍历物品更好理解。

那么我先给出先遍历物品，然后遍历背包重量的代码。

1
2
3
4
5
6
7
8
// weight数组的大小 就是物品个数
for(int i = 1; i < weight.size(); i++) { // 遍历物品
    for(int j = 0; j <= bagweight; j++) { // 遍历背包容量
        if (j < weight[i]) dp[i][j] = dp[i - 1][j];
        else dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);

    }
}

先遍历背包，再遍历物品，也是可以的！（注意我这里使用的二维dp数组）

例如这样：

1
2
3
4
5
6
7
// weight数组的大小 就是物品个数
for(int j = 0; j <= bagweight; j++) { // 遍历背包容量
    for(int i = 1; i < weight.size(); i++) { // 遍历物品
        if (j < weight[i]) dp[i][j] = dp[i - 1][j];
        else dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
    }
}

滚动数组优化：

1
2
3
4
5
6
for(int i = 0; i < weight.size(); i++) { // 遍历物品
    for(int j = bagWeight; j >= weight[i]; j--) { // 遍历背包容量
        dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);

    }
}

完整代码：

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
47
48
49
50
51
52
53
54
55
56
57
public class BagProblem {
    public static void main(String[] args) {
        int[] weight = {1,3,4};
        int[] value = {15,20,30};
        int bagSize = 4;
        testWeightBagProblem(weight,value,bagSize);
    }

    /**
     * 动态规划获得结果
     * @param weight  物品的重量
     * @param value   物品的价值
     * @param bagSize 背包的容量
     */
    public static void testWeightBagProblem(int[] weight, int[] value, int bagSize){

        // 创建dp数组
        int goods = weight.length;  // 获取物品的数量
        int[][] dp = new int[goods][bagSize + 1];

        // 初始化dp数组
        // 创建数组后，其中默认的值就是0
        for (int j = weight[0]; j <= bagSize; j++) {
            dp[0][j] = value[0];
        }

        // 填充dp数组
        for (int i = 1; i < weight.length; i++) {
            for (int j = 1; j <= bagSize; j++) {
                if (j < weight[i]) {
                    /**
                     * 当前背包的容量都没有当前物品i大的时候，是不放物品i的
                     * 那么前i-1个物品能放下的最大价值就是当前情况的最大价值
                     */
                    dp[i][j] = dp[i-1][j];
                } else {
                    /**
                     * 当前背包的容量可以放下物品i
                     * 那么此时分两种情况：
                     *    1、不放物品i
                     *    2、放物品i
                     * 比较这两种情况下，哪种背包中物品的最大价值最大
                     */
                    dp[i][j] = Math.max(dp[i-1][j] , dp[i-1][j-weight[i]] + value[i]);
                }
            }
        }

        // 打印dp数组
        for (int i = 0; i < goods; i++) {
            for (int j = 0; j <= bagSize; j++) {
                System.out.print(dp[i][j] + "\t");
            }
            System.out.println("\n");
        }
    }
}

2. 例题 0-1背包问题

2.1 分割等和子集 (416)

给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。

示例 1：

1
2
3
输入：nums = [1,5,11,5]
输出：true
解释：数组可以分割成 [1, 5, 5] 和 [11] 。

示例 2：

1
2
3
输入：nums = [1,2,3,5]
输出：false
解释：数组不能分割成两个元素和相等的子集。

提示：

  • 1 <= nums.length <= 200
  • 1 <= nums[i] <= 100

根据题意，可以转化为是否能够从集合中选出元素使得元素的和是集合所有元素和的一半

定义dp[i][j]为从前i个元素中选取几个，是否能够使得和为j

因此采用boolean

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public boolean canPartition(int[] nums) {
        if(nums.length==1)return false;
        if(nums.length==2)return nums[0]==nums[1];
        int sum = 0;
        for(int i=0;i<nums.length;i++){
            sum += nums[i];
        }
        if(sum%2!=0)return false;
        sum /= 2;
        boolean[][] dp = new boolean[nums.length][sum+1];
        dp[0][nums[0]] = true;
        for(int i=1;i<nums.length;i++){
            for(int j=1;j<=sum;j++){
                if(dp[i][sum])return true;
                dp[i][j] = dp[i-1][j] || (j>nums[i]?dp[i-1][j-nums[i]]:false);
            }
        }
        return dp[nums.length-1][sum];
    }
}

滚动数组优化：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public boolean canPartition(int[] nums) {
        if(nums.length==1)return false;
        if(nums.length==2)return nums[0]==nums[1];
        int sum = 0;
        for(int i=0;i<nums.length;i++){
            sum += nums[i];
        }
        if(sum%2!=0)return false;
        sum /= 2;
        boolean[] dp = new boolean[sum+1];
        dp[nums[0]] = true;
        for(int i=1;i<nums.length;i++){
            for(int j=sum;j>=1;j--){
                dp[j] = dp[j] || (j>nums[i]?dp[j-nums[i]]:false);
            }
        }
        return dp[sum];
    }
}

2.2 最后一块石头的重量 II (1049)

有一堆石头，用整数数组 stones 表示。其中 stones[i] 表示第 i 块石头的重量。

每一回合，从中选出任意两块石头，然后将它们一起粉碎。假设石头的重量分别为 x 和 y，且 x <= y。那么粉碎的可能结果如下：

  • 如果 x == y，那么两块石头都会被完全粉碎；
  • 如果 x != y，那么重量为 x 的石头将会完全粉碎，而重量为 y 的石头新重量为 y-x。

最后，最多只会剩下一块 石头。返回此石头 最小的可能重量 。如果没有石头剩下，就返回 0。

示例 1：

1
2
3
4
5
6
7
输入：stones = [2,7,4,1,8,1]
输出：1
解释：
组合 2 和 4，得到 2，所以数组转化为 [2,7,1,8,1]，
组合 7 和 8，得到 1，所以数组转化为 [2,1,1,1]，
组合 2 和 1，得到 1，所以数组转化为 [1,1,1]，
组合 1 和 1，得到 0，所以数组转化为 [1]，这就是最优值。

示例 2：

1
2
输入：stones = [31,26,33,21,40]
输出：5

相当于给背包设个限制最多装sum/2的重量，看在这个限制下最多能装多少，假设最多能装a,那么剩下的就是sum-a,正反物质相遇湮灭剩下sum-a-a

因为sum/2 <= sum -sum/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
class Solution {
    public int lastStoneWeightII(int[] stones) {
        int sum = 0;
        for(int i=0;i<stones.length;i++){
            sum += stones[i];
        }
        int target = sum/2;
        int[][] dp = new int[stones.length][target+1];
        for(int j=0;j<=target;j++){
            if(j>=stones[0]){
                dp[0][j] = stones[0];
            }
        }
        for(int i=1;i<stones.length;i++){
            for(int j=0;j<=target;j++){
                if(j<stones[i]){
                    dp[i][j] = dp[i-1][j];
                }else{
                    dp[i][j] = Math.max(dp[i-1][j],dp[i-1][j-stones[i]]+stones[i]);
                }
            }
        }
        return sum - 2*dp[stones.length-1][target];
    }
}

3. 完全背包问题

有N件物品和一个最多能背重量为W的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品都有无限个（也就是可以放入背包多次），求解将哪些物品装入背包里物品价值总和最大。

完全背包和01背包问题唯一不同的地方就是，每种物品有无限件。

对于0-1背包而言：

1
2
3
4
5
6
7
8
9
10
11
12
13
// weight数组的大小 就是物品个数
for(int j = 0; j <= bagweight; j++) { // 遍历背包容量
    for(int i = 1; i < weight.size(); i++) { // 遍历物品
        if (j < weight[i]) dp[i][j] = dp[i - 1][j];
        else dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
    }
}
//滚动数组优化版本
for(int i = 0; i < weight.size(); i++) { // 遍历物品
    for(int j = bagWeight; j >= weight[i]; j--) { // 遍历背包容量
        dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
    }
}

对于完全背包而言：

如果你不把这第 i 个物品装入背包，也就是说你不加入第i个 这个价值的物品，那么凑出总价值j 的方法数 dp[i][j] 应该等于 dp[i-1][j]，继承之前的结果。

如果你把这第 i 个物品装入了背包，也就是说你加入第i个 这个价值的物品，那么 dp[i][j] 应该等于 dp[i][j-weight[i]]。若只使用前 i 个物品（可以重复使用），当背包容量为 j-weight[i] 时，有 dp[i][j-weight[i]] 种方法可以装满背包。看到了吗，dp[i][j-weight[i]] 也是允许你使用第 i 个硬币的，所以说已经包含了重复使用硬币的情况。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
//二维形式
for(int i=1;i<= weight.size();i++){
    for(int j=1;j<=bagWeight;j++){
        if(j>=weight[i]){
            dp[i][j] = dp[i-1][j] + dp[i][j-weight[i]];
        }else{
            dp[i][j] = dp[i-1][j];
        }
    }
}
//01背包内嵌的循环是从大到小遍历，为了保证每个物品仅被添加一次。
//而完全背包的物品是可以添加多次的，所以要从小到大去遍历
// 先遍历物品，再遍历背包,滚动数组优化
for(int i = 0; i < weight.size(); i++) { // 遍历物品
    for(int j = weight[i]; j <= bagWeight ; j++) { // 遍历背包容量
        dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);

    }
}

4. 例题 完全背包问题

4.1 零钱兑换 II (518)

给你一个整数数组 coins 表示不同面额的硬币，另给一个整数 amount 表示总金额。

请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额，返回 0 。

假设每一种面额的硬币有无限个。

题目数据保证结果符合 32 位带符号整数。

示例 1：

1
2
3
4
5
6
7
输入：amount = 5, coins = [1, 2, 5]
输出：4
解释：有四种方式可以凑成总金额：
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1

示例 2：

1
2
3
输入：amount = 3, coins = [2]
输出：0
解释：只用面额 2 的硬币不能凑成总金额 3 。

示例 3：

1
2
输入：amount = 10, coins = [10] 
输出：1

提示：

  • 1 <= coins.length <= 300
  • 1 <= coins[i] <= 5000
  • coins 中的所有值 互不相同
  • 0 <= amount <= 5000
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 {
    //dp[j]：凑成总金额j的货币组合数为dp[j]
    public int change(int amount, int[] coins) {
        if(amount==0)return 1;
        int[][] dp = new int[coins.length+1][amount+1];
        for(int j=0;j<=amount;j++){
            dp[0][j] = 0;
        }
        for(int i=0;i<=coins.length;i++){
            dp[i][0] = 1;
        }
        for(int i=1;i<=coins.length;i++){
            for(int j=1;j<=amount;j++){
                if(j>=coins[i-1]){
                    dp[i][j] = dp[i-1][j] + dp[i][j-coins[i-1]];
                }else{
                    dp[i][j] = dp[i-1][j];
                }
            }
        }
        return dp[coins.length][amount];
    }
}

滚动数组优化：

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public int change(int amount, int[] coins) {
        if(amount==0)return 1;
        int[] dp = new int[amount+1];
        dp[0] = 1;
        for(int i=1;i<=coins.length;i++){
            for(int j=coins[i-1];j<=amount;j++){
                dp[j] = dp[j] + dp[j-coins[i-1]];
            }
        }
        return dp[amount];
    }
}

4.2 零钱兑换 (322)

给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。

计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。

你可以认为每种硬币的数量是无限的。

示例 1：

1
2
3
输入：coins = [1, 2, 5], amount = 11
输出：3 
解释：11 = 5 + 5 + 1

示例 2：

1
2
输入：coins = [2], amount = 3
输出：-1

示例 3：

1
2
输入：coins = [1], amount = 0
输出：0

提示：

  • 1 <= coins.length <= 12
  • 1 <= coins[i] <= 231 - 1
  • 0 <= amount <= 104
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int coinChange(int[] coins, int amount) {
        if (amount == 0) return 0;
        int[][] dp = new int[coins.length + 1][amount + 1];
        for (int j = 0; j <= amount; j++) {
            dp[0][j] = Integer.MAX_VALUE;
        }
        for (int i = 1; i <= coins.length; i++) {
            for (int j = 1; j <= amount; j++) {
                if (j - coins[i - 1] >= 0&&dp[i][j-coins[i-1]]!=Integer.MAX_VALUE) {
                    dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - coins[i - 1]] + 1);
                } else {
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }
        if (dp[coins.length][amount] == Integer.MAX_VALUE) return -1;
        return  dp[coins.length][amount];
    }
}

//注意输入[2]， 3的情况

滚动数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int coinChange(int[] coins, int amount) {
        if(amount==0)return 0;
        int[] dp = new int[amount+1];
        dp[0] = 0;
        for(int j=1;j<=amount;j++){
            dp[j] = Integer.MAX_VALUE;
        }
        for(int i=1;i<=coins.length;i++){
            for(int j=coins[i-1];j<=amount;j++){
                if(dp[j-coins[i-1]]!=Integer.MAX_VALUE){
                    dp[j] = Math.min(dp[j],dp[j-coins[i-1]]+1);
                }
            }
        }
        if(dp[amount]==Integer.MAX_VALUE)return -1;
        return dp[amount];
    }
}