动态规划初探

通过“爬楼梯”，简单入门动态规划。

【 爬楼梯】有一座高度是10级台阶的楼梯，从下往上走，每跨一步只能向上1级或者2级台阶，求一共有多少种走法。

思路一：简单递归算法

假设只差一步就走到第十级，则有两种情况：

  • 从第九级走到第十级：最后一步上1级台阶
  • 从第八级走到第十级：最后一步上2级台阶

所以得出问题模型：

  • 十级台阶的走法数 = 九级台阶的走法数 + 八级台阶的走法数
  • 问题建模：F(1) = 1; F(2) = 2; F(n) = F(n-1) + F(n-2) (n>=3);

动态规划中三个重要概念：

  • 最优子结构：例如在 F(10) = F(9) + F(8) 中，F(9) 和 F(8)是 F(10)的 最优子结构
  • 边界：F(1) 和F(2)是边界
  • 状态转移公式：F(n) = F(n-1) + F(n-2)是状态转移公式
1
// 动态规划——爬楼梯
2
/* 递归求解: 时间复杂度：O(2^N),存在太多相同的参数被重新计算*/
3
#include<iostream>
4
using namespace std;
5
int getClimbingWays(int n){
6
    if(n < 1)   return 0;
7
    if(n==1 || n==2)    return n;
8
    return getClimbingWays(n-1) + getClimbingWays(n-2);
9
}
10
int main(){
11
    int n;
12
    cin >> n;
13
    cout << getClimbingWays(n);
14
    return 0;
15
}

思路二：备忘录算法

  • 先创建一个哈希表，每次把不同参数的计算结果存入哈希
  • 当遇到相同参数的时候，直接从哈希表中取出，不用重复计算
1
// 动态规划——爬楼梯
2
/* 备忘录算法: 时间复杂度：O(N),空间复杂度：O(N)
3
             F(1)到F(N)有N个不同输入，哈希表中存放了N-2个结果*/
4
#include<iostream>
5
#include<map>
6
using namespace std;
7
map<int, int> my_map;
8
int getClimbingWays(int n){
9
    if(n < 1)   return 0;
10
    if(n==1 || n==2)    return n;
11
    if(my_map.count(n))     return my_map[n];
12
    else{
13
        int value = getClimbingWays(n-1) + getClimbingWays(n-2);
14
        my_map[n] = value;
15
        return value;
16
    }
17
}
18
int main(){
19
    int n;
20
    cin >> n;
21
    cout << getClimbingWays(n) << endl;;
22
    return 0;
23
}

思路三：真正的动态规划

台阶数 1 2 3 4 5 6 7 8 9 10
走法数 1 2 3 5 8 13 21 34 55 89

逆向思路：因为F(n) = F(n-1) + F(n-2)，即每个台阶数的走法都只与前两个有关，故每次迭代只保留前两个状态即可，以最大化降低空间复杂度。

1
// 动态规划——爬楼梯
2
/* 动态规划求解: 时间复杂度：O(N),空间复杂度：O(1)
3
               利用简洁的自底向上的递推方式，实现时间和空间上的最优*/
4
#include<iostream>
5
using namespace std;
6
int getClimbingWays(int n){
7
    if(n < 1)   return 0;
8
    if(n==1 || n==2)    return n;
9
    int a = 1, b = 2, tmp = 0;
10
    for(int i=3; i<=n; i++){
11
        tmp = a + b;
12
        a = b;
13
        b = tmp;
14
    }
15
    return tmp;
16
}
17
int main(){
18
    int n;
19
    cin >> n;
20
    cout << getClimbingWays(n) << endl;;
21
    return 0;
22
}

【 国王和金矿】有一个国家发现了5座金矿，每座金矿的黄金储量不同，需要参与挖掘的工人数也不同。参与挖矿工人的总数是10人。每座金矿要么全挖，要么不挖，不能派出一半人挖取一半金矿。要求用程序求解出，要想得到尽可能多的黄金，应该选择挖取哪几座金矿？5座金矿分别为：400金/5人、500金/5人、200金/3人、300金/4人、350金/3人

动态规划分析

  • 最优子结构：10人挖前4座金矿(此时不挖第5座金矿) 和 10-3人挖前4座金矿(第5座金矿剩余3人挖)。所以挖5座金矿的最优选择是上面两者挖金数量的最大值。
    • 设金矿数为N，工人数为W，各金矿黄金数设为数组G[]，金矿用工量设为数组P[]
    • 5座金矿与4座金矿的最优选择关系：F(5,10) = MAX(F(4,10), F(4,10-P[4])+G[4])
  • 边界：按照工人数是否足够一座金矿的用工量分两种情况：
    • 当N=1，W>=P[0]时，F(N,W) = G[0]
    • 当N=1，W<P[0]时，F(N,W) 0
  • 状态转移公式：
    • F(n,w) = 0 (n<=1, w<p[0]);
    • F(n,w) = g[0] (n==1, w>=p[0]);
    • F(n,w) = F(n-1,w) (n>1, w<p[n-1])
    • F(n,w) = max(F(n-1,w), F(n-1,w-p[n-1]) + g[n-1]) (n>1, w>=p[n-1])
工人数 1 2 3 4 5 6 7 8 9 10
1座金矿 0 0 0 0 400 400 400 400 400 400
2座金矿 0 0 0 0 500 500 500 500 500 900
3座金矿 0 0 200 200 500 500 500 700 700 900
4座金矿 0 0 200 300 500 500 500 700 800 900
5座金矿 0 0 350 350 500 550 650 850 850 900 
1
// 动态规划——挖黄金
2
/* 动态规划求解: 时间复杂度：O(n*w),空间复杂度：O(w)*/
3
#include<iostream>
4
#include<vector>
5
using namespace std;
6
int getMostGold(int n, int w, int g[], int p[]){
7
    int preResults[w+1], Results[w+1];
8
    for(int i=1; i<=w; i++) //填充边界格子
9
        if(i<p[0])  preResults[i] = 0; //分配人数少于第i座金矿的用工量
10
        else preResults[i] = g[0];
11
    for(int i=1; i<n; i++){  //从第2座金矿开始计算
12
        for(int j=1; j<=w; j++)
13
            if(j < p[i])    Results[j] = preResults[j];
14
            else Results[j] = max(preResults[j], preResults[j-p[i]] + g[i]);
15
        for(int i=1; i<=w; i++)
16
            preResults[i] = Results[i];
17
    }
18
    return Results[w];
19
}
20
int main(){
21
    int n=5, w=10; //金矿数、工人数
22
    int g[] = {400, 500, 200, 300, 350}; //各金矿的黄金数
23
    int p[] = {5, 5, 3, 4, 3}; //各金矿的用工量
24
    cout << getMostGold(n, w, g, p) << endl;;
25
    return 0;
26
}

注意点：

  • 动态规划方法的时间和空间都和W成正比
  • 简单递归算法和W不相关
  • 所以当工人数W很大时，动态规划反而不如简单递归

漫画：什么是动态规划？
常见的动态规划问题分析与求解