算法学习——动态规划

动态规划，英文：Dynamic Programming，简称DP，如果某一问题有很多重叠子问题，使用动态规划是最有效的，动态规划中每一个状态一定是由上一个状态推导出来的。所以动态规划问题的解题关键就是找出当前状态与上个状态之间的关系。

动态规划问题的主要解题步骤：

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

本篇主要关于几个常见动态规划算法案例

一、楼梯问题

1.1 爬楼梯问题（Leetcode70）

1.1.1 问题描述

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

示例 ：
输入： n = 2
输出： 2
解释： 有两种方法可以爬到楼顶。

  1. 1 阶 + 1 阶
  2. 2 阶

1.1.2 解决思想

在该问题中，到达第1层台阶只有一种方法，即直接走一步，到达第2级台阶共有两种方法：1.先走一步，再走一步，2.直接走两步。
从第三级台阶开始，由于每次只能走一级或两级台阶，所以我们只能从该级台阶的前一级台阶或前两级台阶到达该级台阶。
如：到达3级台阶只能由第1级台阶出发一次走两步，或从第2级台阶出发直接走一步到达3级台阶，所以到达第3级台阶的方法数为到达第1级台阶的方法数+到达第2级台阶的方法数。
根据以上思想，我们可以
1.设置dp数组dp[i]，其中dp[i]表示到达第i级台阶的方法数；
2.dp[i]可由dp[i-1]和dp[i-2]推导而来，dp[i]=dp[i-2]+dp[i-1]；
3.关于初始化，因为当i=0时无意义，所以初始化应为dp[1]=1,dp[2]=2；
4.由于dp[i]是由前面两个数据推导而来，所以应该从前往后遍历。

1.1.3 最终代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int climbStairs(int n) {
    if (n <= 2) {
        return n;
    }
    int i;
    // dp数组，其中dp[i]表示到达第i级台阶的方法数
    int* dp = (int*)malloc(sizeof(int) * (n + 1));
    dp[1] = 1;
    dp[2] = 2;
    // i<=2会造成dp数组无意义或越界，所以应从3开始遍历
    for (i = 3; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    return dp[n];
}

1.2 使用最小体力爬楼梯（Leetcode746）

1.2.1 问题描述

给你一个整数数组 cost ，其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用，即可选择向上爬一个或者两个台阶。
你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。
请你计算并返回达到楼梯顶部的最低花费。

示例 1：
输入：cost = [10,15,20]
输出：15
解释：你将从下标为 1 的台阶开始。

  • 支付 15 ，向上爬两个台阶，到达楼梯顶部。
    总花费为 15 。

示例 2：
输入：cost = [1,100,1,1,1,100,1,1,100,1]
输出：6
解释：你将从下标为 0 的台阶开始。

  • 支付 1 ，向上爬两个台阶，到达下标为 2 的台阶。
  • 支付 1 ，向上爬两个台阶，到达下标为 4 的台阶。
  • 支付 1 ，向上爬两个台阶，到达下标为 6 的台阶。
  • 支付 1 ，向上爬一个台阶，到达下标为 7 的台阶。
  • 支付 1 ，向上爬两个台阶，到达下标为 9 的台阶。
  • 支付 1 ，向上爬一个台阶，到达楼梯顶部。
    总花费为 6 。

1.2.2 解决思想

该问题与上一问题类似，本问题中到达第i级台阶也只有两种方案：1.由第i-2级台阶走一步，2.由第i-1级台阶走一步，所以到达第i级台阶的最小花费就是从第i-1级台阶上来还是从第i-2级台阶上来。
根据以上思想，我们可以
1.设置dp数组dp[i]，其中dp[i]表示到达第i级台阶的最小体力花费;
2.dp[i]可由dp[i-1]和dp[i-2]推导而来，dp[i]=fmin(dp[i-2]+cost[i-2],dp[i-1]+dp[i-1]);
3.关于初始化，因为你选择从下标为 0 或下标为 1 的台阶开始爬楼梯，所以dp[0]=0,dp[1]=0，即到达第0级和第1级台阶不消耗体力;
4.由于dp[i]是由前面两个数据推导而来，所以应该从前往后遍历。

1.2.3 最终代码

1
2
3
4
5
6
7
8
9
10
11
12
int minCostClimbingStairs(int* cost, int costSize) {
    // dp[i]表示到达i位置所需要的最小体力
    int* dp = (int*)malloc(sizeof(int) * (costSize + 1));
    //初始位置可以使0或者1，所以dp[0]和dp[1]都为0
    dp[0] = 0;
    dp[1] = 0;
    for (int i = 2; i <= costSize; i++) {
        // 从前前一个台阶往上跳花费为dp[i - 2] + cost[i - 2]，从前一个台阶往上跳花费为dp[i - 1] + cost[i - 1]，选择其中最小花费
        dp[i] = fmin(dp[i - 1] + cost[i - 1],dp[i - 2] + cost[i - 2]);
    }
    return dp[costSize];
}

二、背包问题

2.1 0-1背包问题（二维数组）

2.1.1 问题描述

0-1背包问题：有n件物品和一个最多能背重量为 w 的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大。
例：
背包最大重量为4，有三种物品，其重量与价值分别为：

物品 重量 价值
0 1 15
1 3 20
2 4 30
问背包能背的物品最大价值是多少？

2.1.2 解决思想

0-1背包中，对于每种物品只能选择一次，所以对于每种物品只有两种情况：1.选择物品i，消耗掉背包容量weight[i]，总价值增加value[i]
2.不选择物品i，背包容量与总价值不变
所以根据以上思想，我们可以：
1.首先创建二维dp数组dp[i][j]，dp[i][j]表示在编号0到i的物品中背包容量为j时所能得到的最大价值。
2.dp[i][j]可由两种情况得到：a.选择物品i，最终结果为dp[i-1][j-weight[i]]+value[i]，b.不选择物品i，背包容量和最终价值不变，最终结果为dp[i-1][j]，所以最终dp[i][j]=fmax(dp[i-1][j-weight[i]]+value[i],dp[i-1][j])
3.初始化：当j<weight[0]的时候，dp[0][j] 应该是 0，因为背包容量比编号0的物品重量还小。当j>=weight[0]时，dp[0][j] 应该是value[0]，因为背包容量放足够放编号0物品。

初始化后：

背 包 容 量
0 1 2 3 4
物品0 0 15 15 15 15
物品1 0 0 0 0 0
物品2 0 0 0 0 0

4.由递推公式可以看出，dp[i][j]是由表格上边和左边数据得出的，所以应该从前往后遍历，至于i和j的先后顺序，因为不管是先i后j还是先j后i，都可以在得到dp[i][j]前得出其左上部分数据，所以遍历i,j的先后顺序无所谓

2.1.3 最终代码

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
58
59
60
61
62
63
64
65
66
67
68
69
void bag0_1(int *weight, int weightSize, int *cost, int costSize, int bagWeight) {
    // 定义dp数组，dp[i][j]含义为[0,i]号物品放入容量为j的背包里的最大价值
    // 横坐标表示物品编号，纵坐标表示背包当前容量
    /*dp数组
               背包容量
             0  1  2  3  4
     物品0
     物品1
     物品2
     */
    int dp[weightSize][bagWeight + 1];
    int i, j;
    // 先全部初始化为0
    /*dp数组
               背包容量
            0  1  2  3  4
    物品0    0  0  0  0  0
    物品1    0  0  0  0  0
    物品2    0  0  0  0  0
    */
    for (i = 0; i < weightSize; i++) {
        for (j = 0; j <= bagWeight; j++) {
            dp[i][j] = 0;
        }
    }
    // 初始化dp数组第一行
    /*dp数组
                背包容量
            0   1   2   3   4
    物品0    0  15  15  15  15
    物品1    0  0   0   0   0
    物品2    0  0   0   0   0
    */
    for (j = weight[0]; j <= bagWeight; j++) {
        dp[0][j] = cost[0];
    }
    printf("----------init----------\n");
    for (i = 0; i < weightSize; i++) {
        for (j = 0; j <= bagWeight; j++) {
            printf("%2d ",dp[i][j]);
        }
        printf("\n");
    }
    printf("----------final----------\n");
    for (i = 1; i < weightSize; i++) {
        for (j = 1; j <= bagWeight; j++) {
            // 不进行判断的话会造成dp[i - 1][j - weight[i]] + cost[i]中dp数组越界，j-weight[i]<0
            // 如果当前背包容量小于物品重量
            if (j < weight[i]){
                // 背包物品的价值等于背包不放置当前物品时的价值
                dp[i][j] = dp[i - 1][j];
            }
            // 若背包当前重量可以放置物品
            else{
                // 背包的价值等于放置该物品或不放置该物品的最大值
                dp[i][j] = fmax(dp[i - 1][j], dp[i - 1][j - weight[i]] + cost[i]);
            }

        }
    }
    /*最终dp数组
                背包容量
            0   1   2   3   4
    物品0    0  15  15  15  15
    物品1    0  15  15  20  35
    物品2    0  15  15  20  35
    */
    printf("%d\n", dp[weightSize - 1][bagWeight]);
}

2.2 0-1背包问题（滚动数组）

2.2.1 问题描述

0-1背包问题：有n件物品和一个最多能背重量为 w 的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大。
例：
背包最大重量为4，有三种物品，其重量与价值分别为：

物品 重量 价值
0 1 15
1 3 20
2 4 30
问背包能背的物品最大价值是多少？

2.2.2 解决思想

由上面二维数组的解决办法我们可以看出，dp[i][j]的取值来源于表格的左上方部分，所以我们可以使用一维数组进行优化，通过下一层数据覆盖上一层数据从而得到最终的结果
所以根据以上思想，我们可以：
1.首先创建一维dp数组dp[j]，定义dp数组，dp[j]含义为[0,i]号物品放入容量为j的背包里的最大价值
2.与二维数组类似，dp[j]来源有两种情况：即取物品j（dp[j - weight[i]] + cost[i]）或不取物品j(dp[j])，则递推公式为：dp[j] = fmax(dp[j], dp[j - weight[i]] + cost[i])
3.对于一维数组的初始化，dp[0]表示背包容量为0，所以dp[0]=0，由于递推公式为dp[j] = fmax(dp[j], dp[j - weight[i]] + cost[i])，所以dp[j]是取两者之间的最大值，因为不可能为负数，所以我们直接将dp数组全部初始化为0即可
初始化后：

背 包 容 量
0 1 2 3 4
物品0 0 0 0 0 0

4.对于一维数组的遍历顺序，由于dp[j]的计算需要用到dp[j]左侧的数据，所以我们不能从前往后遍历，否则会影响该轮的判断，举一个例子：
假设从前往后遍历数组，第一遍遍历时，由于dp初始化全为0，所以dp[0]=0,dp[1]=fmax(dp[1],dp[1-1]+15)=fmax(0,15)=15，当j=2时，dp[2]=fmax(dp[2],dp[2-1]+15)=fmax(0,30)=30，这就使得物品1被取了两次，这与题目要求是不符合的，出现此情况的原因是从前往后遍历时，每次取物品都是从0号物品开始取，没有考虑物品0是否被取过，从而使得物品重复使用
当我们从后往前遍历时，如dp[2]=fmax(dp[2],dp[2-1]+15)=fmax(dp[2],dp[1]+15)，因为dp[1]还未更新所以不会使得物品0被装入两次，所以需要从后往前遍历

2.2.3 最终代码

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
//滚动数组
void bag0_1(int *weight, int weightSize, int *cost, int costSize, int bagWeight) {
    //定义dp数组，dp[j]含义为[0,i]号物品放入容量为j的背包里的最大价值
    //横坐标表示物品编号，纵坐标表示背包当前容量
    /*dp数组
               背包容量
             0  1  2  3  4
     物品i
     */
    int dp[bagWeight + 1];
    int i, j;
    //先全部初始化为0
    /*dp数组
           背包容量
            0  1  2  3  4
    物品0    0  0  0  0  0
    */
    for (j = 0; j <= bagWeight; j++) {
        dp[j] = 0;
    }
    //这里j需要从后往前遍历是因为从前往后遍历的话会导致同一物品多次放入
    //如i=0时，dp[0]=0,dp[1]=max(dp[1],dp[1-1]+cost[1])=max(0,0+15)=15,dp[2]=max(dp[2],dp[2-1]+cost[1])=max(15,30)=30,
    //这就使得重量为1的物品0放入了两次
    for (i = 0; i < weightSize; i++) {
        for (j = bagWeight; j >= weight[i]; j--){
            //与二维数组不同，此处无需判断j与weight[i]关系，因为从后往前遍历，j一定大于weight[i],不会造成数组越界
                dp[j] = fmax(dp[j], dp[j - weight[i]] + cost[i]);
        }
    }
    /*最终dp数组
                背包容量
            0   1   2   3   4
    物品i    0  15  15  20  35
    */
    printf("%d\n", dp[bagWeight]);
}

2.3 完全背包问题

2.2.1 问题描述

完全背包问题：有n件物品和一个最多能背重量为 w 的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品可以装入多个，求解将哪些物品装入背包里物品价值总和最大。
例：
背包最大重量为4，有三种物品，其重量与价值分别为：

物品 重量 价值
0 1 15
1 3 20
2 4 30
问背包能背的物品最大价值是多少？

2.2.2 解决思想

完全背包问题与0-1背包问题的不同之处在于，完全背包问题可以装入多个相同物品，其实就是滚动数组的正序遍历版本

2.2.3 最终代码

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
//完全背包问题
void bag0_1(int *weight, int weightSize, int *cost, int costSize, int bagWeight) {
    //定义dp数组，dp[j]含义为[0,i]号物品放入容量为j的背包里的最大价值
    //横坐标表示物品编号，纵坐标表示背包当前容量
    /*dp数组
               背包容量
             0  1  2  3  4
     物品i
     */
    int dp[bagWeight + 1];
    int i, j;
    //先全部初始化为0
    /*dp数组
           背包容量
            0  1  2  3  4
    物品0    0  0  0  0  0
    */
    for (j = 0; j <= bagWeight; j++) {
        dp[j] = 0;
    }
    //这里j需要从前往后遍历，才能实现同一物品放入多次的要求
    for (i = 0; i < weightSize; i++) {
        for (j = weight[i]; j <= bagWeight; j++){
                dp[j] = fmax(dp[j], dp[j - weight[i]] + cost[i]);
        }
    }
    /*最终dp数组
                背包容量
            0   1   2   3   4
    物品i    0  15  30  45  60
    */
    printf("%d\n", dp[bagWeight]);
}