Day39——Dp专题

---

01背包

01背包：每一个物品只能选一次，选或者不选

状态标识：f[i][j]：所有只考虑前i个物品，且总体积不超j的所有选法的集合

属性：Max

状态计算：f[i][j]

• w[i]代表重量，v[i]代表价值

• 不选第i个物品：f[i][j] = f[i - 1][j]

• 选第i个物品：f[i][j] = f[i - 1][j - w[i]] + v[i]

二维数组

	for(int i = 1; i <= n; i ++){
        for(int j = 0; j <= m; j ++){
            f[i][j] = f[i - 1][j];
            if(j >= w[i]){
                f[i][j] = Math.max(f[i][j], f[i - 1][j - w[i]] + v[i]);
            }
        }
    }
1
2
3
4
5
6
7
8

一维数组

	for(int i = 1; i <= n; i ++){
        for(int j = m; j >= w[i]; j --){
            f[j] = Math.max(f[j], f[j - w[i]] + v[i]);
        }
    }
1
2
3
4
5

二维数组

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

动规五部曲

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

dp[i][j] 表示从下标为[0-i]的物品里任意取，放进容量为j的背包，价值总和最大是多少。

• 确定递推公式

不放物品i：

dp[i][j]=dp[i - 1][j]
1

放物品i：

dp[i][j]=dp[i - 1][j - weight[i]] + value[i]
1

递归公式

 dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i])
1

• dp数组如何初始化

状态转移方程 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物品。

for (int j = 0 ; j < weight[0]; j++) {  // 当然这一步，如果把dp数组预先初始化为0了，这一步就可以省略，但很多同学应该没有想清楚这一点。
    dp[0][j] = 0;
}
// 正序遍历
for (int j = weight[0]; j <= bagweight; j++) {
    dp[0][j] = value[0];
}
1
2
3
4
5
6
7

dp[0][j] 和 dp[i][0] 都已经初始化了，那么其他下标应该初始化多少呢

将其余都置为0

• 确定遍历顺序

先遍历物品或者后遍历物品偶都可以运行通过

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

	for(int i = 1; i <= n; i ++){
        for(int j = 0; j <= m; j ++){
            f[i][j] = f[i - 1][j];
            if(j >= w[i]){
                f[i][j] = Math.max(f[i][j], f[i - 1][j - w[i]] + v[i]);
            }
        }
    }
1
2
3
4
5
6
7
8

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

	for(int j = 0; j <= m; j ++){
        for(int i = 1; i <= n; i ++){
            f[i][j] = f[i - 1][j];
            if(j >= w[i]){
                f[i][j] = Math.max(f[i][j], f[i - 1][j - w[i]] + v[i]);
            }
        }
    }
1
2
3
4
5
6
7
8

只要左上角和正上方有值就可以，所以先遍历背包或者先遍历物品都可以

• 举例推导dp数组

Code

  public static void main(String[] args) {
        int[] weight = {1, 3, 4};
        int[] value = {15, 20, 30};
        int bagsize = 4;
        dfs(weight, value, bagsize);
    }

    public static void dfs(int[] weight, int[] value, int bagsize){
        int wlen = weight.length, value0 = 0;
        //定义dp数组：dp[i][j]表示背包容量为j时，前i个物品能获得的最大价值
        int[][] dp = new int[wlen + 1][bagsize + 1];
        //初始化：背包容量为0时，能获得的价值都为0
        for (int i = 0; i <= wlen; i++){
            dp[i][0] = value0;
        }
        //遍历顺序：先遍历物品，再遍历背包容量
        for (int i = 1; i <= wlen; i++){
            for (int j = 1; j <= bagsize; j++){
                if (j < weight[i - 1]){
                    dp[i][j] = dp[i - 1][j];
                }else{
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weight[i - 1]] + value[i - 1]);
                }
            }
        }
        //打印dp数组
        for (int i = 0; i <= wlen; i++){
            for (int j = 0; j <= bagsize; j++){
                System.out.print(dp[i][j] + " ");
            }
            System.out.print("\n");
        }
    }
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

一维数组

动规五部曲分析如下：

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

在一维dp数组中，dp[j]表示：容量为j的背包，所背的物品价值可以最大为dp[j]。

• dp数组的递推公式

dp[j]有两个选择，一个是取自己dp[j] 相当于 二维dp数组中的dp[i-1][j]，即不放物品i，一个是取dp[j - weight[i]] + value[i]，即放物品i，指定是取最大的，毕竟是求最大价值

dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
1

• dp数组的初始化

dp数组在推导的时候一定是取价值最大的数，如果题目给的价值都是正整数那么非0下标都初始化为0就可以了。

这样才能让dp数组在递归公式的过程中取的最大的价值，而不是被初始值覆盖了。

那么我假设物品价值都是大于0的，所以dp数组初始化的时候，都初始为0就可以了

• dp数组的遍历顺序

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

这里大家发现和二维dp的写法中，遍历背包的顺序是不一样的！

二维dp遍历的时候，背包容量是从小到大，而一维dp遍历的时候，背包是从大到小。

为什么呢？

倒序遍历是为了保证物品i只被放入一次！。但如果一旦正序遍历了，那么物品0就会被重复加入多次！

举一个例子：物品0的重量weight[0] = 1，价值value[0] = 15

如果正序遍历

dp[1] = dp[1 - weight[0]] + value[0] = 15

dp[2] = dp[2 - weight[0]] + value[0] = 30

倒序就是先算dp[2]

dp[2] = dp[2 - weight[0]] + value[0] = 15 （dp数组已经都初始化为0）

dp[1] = dp[1 - weight[0]] + value[0] = 15

所以从后往前循环，每次取得状态不会和之前取得状态重合，这样每种物品就只取一次了。

一维数组必须先遍历背包，之后在遍历背包容量

因为一维dp的写法，背包容量一定是要倒序遍历（原因上面已经讲了），如果遍历背包容量放在上一层，那么每个dp[j]就只会放入一个物品，即：背包里只放入了一个物品。

倒序遍历的原因是，本质上还是一个对二维数组的遍历，并且右下角的值依赖上一层左上角的值，因此需要保证左边的值仍然是上一层的，从右向左覆盖。

• 举例推导dp数组

Code

 public static void main(String[] args) {
        int[] weight = {1, 3, 4};
        int[] value = {15, 20, 30};
        int bagWight = 4;
        dfs(weight, value, bagWight);
    }

    public static void dfs(int[] weight, int[] value, int bagWeight){
        int wLen = weight.length;
        //定义dp数组：dp[j]表示背包容量为j时，能获得的最大价值
        int[] dp = new int[bagWeight + 1];
        //遍历顺序：先遍历物品，再遍历背包容量
        for (int i = 0; i < wLen; i++){
            for (int j = bagWeight; j >= weight[i]; j--){
                dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);
            }
        }
        //打印dp数组
        for (int j = 0; j <= bagWeight; j++){
            System.out.print(dp[j] + " ");
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

面试题目

就是本文中的题目，要求先实现一个纯二维的01背包，如果写出来了，然后再问为什么两个for循环的嵌套顺序这么写？反过来写行不行？再讲一讲初始化的逻辑。

然后要求实现一个一维数组的01背包，最后再问，一维数组的01背包，两个for循环的顺序反过来写行不行？为什么？

注意以上问题都是在候选人把代码写出来的情况下才问的。

二维数组

• for循环遍历顺序不受限制，可以先遍历背包，也可以先遍历背包容量
• 正序遍历，倒叙遍历都可以
• 初始化

for (int j = 0 ; j < weight[0]; j++) {  // 当然这一步，如果把dp数组预先初始化为0了，这一步就可以省略，但很多同学应该没有想清楚这一点。
    dp[0][j] = 0;
}
// 正序遍历
for (int j = weight[0]; j <= bagweight; j++) {
    dp[0][j] = value[0];
}
1
2
3
4
5
6
7

一维数组

• 必须先遍历背包，之后遍历背包容量
• 必须倒叙遍历
• 初始化——都初始化为0

6.整数拆分

力扣题目链接

思路：

动规五部曲：

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

dp[i]：分拆数字i，可以得到的最大乘积为dp[i]。

• 确定递推公式

一个是j * (i - j) 直接相乘。

一个是j * dp[i - j]，相当于是拆分(i - j)，对这个拆分不理解的话，可以回想dp数组的定义。

• dp数组如何初始化

初始化dp[2] = 1

• 确定遍历顺序

dp[i] 是依靠 dp[i - j]的状态，所以遍历i一定是从前向后遍历，先有dp[i - j]再有dp[i]。

for (int i = 3; i <= n ; i++) {
    for (int j = 1; j <= i / 2; j++) {
        dp[i] = max(dp[i], max((i - j) * j, dp[i - j] * j));
    }
}
1
2
3
4
5

• 举例推导dp数组

Code

class Solution {
    public int integerBreak(int n) {
        //dp[i] 为正整数 i 拆分后的结果的最大乘积
        int[]dp=new int[n+1];
        dp[2]=1;
        for(int i=3;i<=n;i++){
            for(int j=1;j<=i-j;j++){
                // 这里的 j 其实最大值为 i-j,再大只不过是重复而已，
                //并且，在本题中，我们分析 dp[0], dp[1]都是无意义的，
                //j 最大到 i-j,就不会用到 dp[0]与dp[1]
                dp[i]=Math.max(dp[i],Math.max(j*(i-j),j*dp[i-j]));
                // j * (i - j) 是单纯的把整数 i 拆分为两个数 也就是 i,i-j ，再相乘
                //而j * dp[i - j]是将 i 拆分成两个以及两个以上的个数,再相乘。
            }
        }
        return dp[n];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

7.不同的二叉搜索

力扣题目链接

思路：

当n为3的时候，有5颗二叉搜索树

dp[3]，就是 元素1为头结点搜索树的数量 + 元素2为头结点搜索树的数量 + 元素3为头结点搜索树的数量

元素1为头结点搜索树的数量 = 右子树有2个元素的搜索树数量 * 左子树有0个元素的搜索树数量

元素2为头结点搜索树的数量 = 右子树有1个元素的搜索树数量 * 左子树有1个元素的搜索树数量

元素3为头结点搜索树的数量 = 右子树有0个元素的搜索树数量 * 左子树有2个元素的搜索树数量

有2个元素的搜索树数量就是dp[2]。

有1个元素的搜索树数量就是dp[1]。

有0个元素的搜索树数量就是dp[0]。

所以dp[3] = dp[2] * dp[0] + dp[1] * dp[1] + dp[0] * dp[2]

如图所示：

动规五部曲：

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

dp[i] ： 1到i为节点组成的二叉搜索树的个数为dp[i]。

• 确定递推公式

递推公式：dp[i] += dp[j - 1] * dp[i - j]; ，j-1 为j为头结点左子树节点数量，i-j 为以j为头结点右子树节点数量

• dp数组如何初始化

初始化dp[0] = 1 dp[1]=1

  dp[0] = 1;
  dp[1] = 1;
1
2

• 确定遍历顺序

从递归公式：dp[i] += dp[j - 1] * dp[i - j]可以看出，节点数为i的状态是依靠 i之前节点数的状态。

那么遍历i里面每一个数作为头结点的状态，用j来遍历

for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= i; j++) {
        dp[i] += dp[j - 1] * dp[i - j];
    }
}
1
2
3
4
5

• 举例推导dp数组

Code

class Solution {
    public int numTrees(int n) {
        int[] dp = new int[n+1];
        dp[0] = 1;
        dp[1] = 1;
        for(int i = 2; i <= n; i++){
            for(int j = 1; j <= i; j++){
                dp[i]+=dp[j-1]*dp[i-j];
            }
        }
        return dp[n];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13