Dynamic programming 动态规划算法

Author Avatar
Jiawen Zhang Aug 14, 2018

动态规划算法在编程题中运用场景很广(我觉得也有点难:( )，这篇博文主要总结了动态规划算法的基本思想以及一些例题。

一、基本概念

动态规划过程是：每次决策依赖于当前状态，又随即引起状态的转移。一个决策序列就是在变化的状态中产生出来的，所以，这种多阶段最优化决策解决问题的过程就称为动态规划。

二、基本思想与策略

动态规划算法与分治法的区别：适合于用动态规划法求解的问题，经分解后得到的子问题往往不是互相独立的（即下一个子阶段的求解是建立在上一个子阶段的解的基础上，进行进一步的求解）。

动态规划算法将待求解的问题分解为若干个子阶段，按顺序求解子阶段，前一子问题的解决为后一子问题的求解提供了有用信息。在求解任一子问题时，列出各种可能的局部解，通过决策保留那些有可能达到最优的局部解，丢弃其他局部解。依次解决各子问题，最后一个子问题就是初始问题的解。

由于动态规划解决的问题多数有重叠子问题这个特点，为减少重复计算，对每一个子问题只解一次，将其不同阶段的不同状态保存在一个二维数组中。

三、适用情况

一般动态规划问题具有三个性质：

  1. 最优化原理：如果问题的最优解所包含的子问题的解也是最优的，就称该问题具有最优子结构，即满足最优化原理。
  2. 无后效性：即某阶段状态一旦确定，就不受这个状态以后决策的影响。也就是说，某状态以后的过程不会影响以前的状态，只与当前状态有关。
  3. 有重叠子问题：即子问题之间是不独立的，一个子问题在下一阶段决策中可能被多次使用到。（该性质并不是动态规划适用的必要条件，但是如果没有这条性质，动态规划算法同其他算法相比就不具备优势）有些子问题会被重复计算多次。动态规划算法正是利用了这种子问题的重叠性质，对每一个子问题只计算一次，然后将其计算结果保存在一个表格中，当再次需要计算已经计算过的子问题时，只是在表格中简单地查看一下结果，从而获得较高的效率。

note:先创建一个哈希表，将每次不同参数的计算结果存入哈希表，当遇到相同参数时，再从哈希表里取出，就避免了重复计算【备忘录算法】

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
//上台阶问题中运用备忘录算法
int getClimbingWays(int n, HashMap<Integer, Integer> map){
    if(n<1){
        return 0;
    }
    if(n==1){
        return 1;
    }
     if(n==2){
        return 2;
    }
     if(map.contains(n)){
        return map.get(n);
    }else{
        int value = getClimbingWays(n-1) + getClimbingWays(n-2);
        map.put(n,value);
        return value;
    }
}

四、求解的基本步骤

动态规划所处理的问题是一个多阶段决策问题，一般由初始状态开始，通过对中间阶段决策的选择，达到结束状态。这些决策形成了一个决策序列，同时确定了完成整个过程的一条活动路线(通常是求最优的活动路线)。如下所示。动态规划的设计都有着一定的模式，一般要经历以下几个步骤。

初始状态 -> |决策1| -> |决策2| -> ... |决策n| -> 结束状态

  1. 划分阶段：按照问题的时间或空间特征，把问题分为若干个阶段。在划分阶段时，注意划分后的阶段一定要是有序的或者是可排序的，否则问题就无法求解。
  2. 确定状态和状态变量：将问题发展到各个阶段时所处于的各种客观情况用不同的状态表示出来。当然，状态的选择要满足无后效性。
  3. 确定决策并写出状态转移方程：因为决策和状态转移有着天然的联系，状态转移就是根据上一阶段的状态和决策来导出本阶段的状态 。所以如果确定了决策，状态转移方程也就可写出。但事实上常常是反过来做，根据相邻两个阶段的状态之间的关系来确定决策方法和状态转移方程。
  4. 寻找边界条件：给出的状态转移方程是一个递推式，需要一个递推的终止条件或边界条件。

一般，只要解决问题的阶段、状态和状态转移决策确定了，就可以写出状态转移方程（包括边界条件）。 实际应用中可以按以下几个简化的步骤进行设计：

  1. 描述最优解的结构
  2. 递归定义最优解的值
  3. 按自底向上的方式计算最优解的值 //此三步构成动态规划解的基础
  4. 由计算出的结果构造一个最优解 //若只要求计算最优解的值可省略

五、算法实现的说明

动态规划的主要难点在于理论上的设计，也就是上面4个步骤的确定，一旦设计完成，实现部分就会非常简单。

 使用动态规划求解问题，最重要的就是确定动态规划三要素：

（1）问题的阶段 （2）每个阶段的状态

（3）从前一个阶段转化到后一个阶段之间的递推关系。

递推关系必须是从次小的问题开始到较大的问题之间的转化，从这个角度来说，动态规划往往可以用递归程序来实现，不过因为递推可以充分利用前面保存的子问题的解来减少重复计算，所以对于大规模问题来说，递归有不可比拟的优势，这也是动态规划算法的核心之处。

确定了动态规划的这三要素，整个求解过程就可以用一个最优决策表来描述，最优决策表是一个二维表，其中行表示决策的阶段，列表示问题状态，表格需要填写的数据一般对应此问题的在某个阶段某个状态下的最优值（如最短路径，最长公共子序列，最大价值等），填表的过程就是根据递推关系，从1行1列开始，以行或者列优先的顺序，依次填写表格，最后根据整个表格的数据通过简单的取舍或者运算求得问题的最优解。

f(n,m)=max{f(n-1,m), f(n-1,m-w[n])+P(n,m)}

六、经典动态算法题

例题一：上台阶问题

有n级台阶，一个人每次上一级或者两级，问有多少种走完n级台阶的方法。

分析：动态规划的实现的关键在于能不能准确合理的用动态规划表来抽象出 实际问题。在这个问题上，我们让f(n)表示走上n级台阶的方法数。

那么当n为1时，f(n) = 1,n为2时，f(n) =2,就是说当台阶只有一级的时候，方法数是一种，台阶有两级的时候，方法数为2。那么当我们要走上n级台阶，必然是从n-1级台阶迈一步或者是从n-2级台阶迈两步，所以到达n级台阶的方法数必然是到达n-1级台阶的方法数加上到达n-2级台阶的方法数之和。即f(n) = f(n-1)+f(n-2)，我们用dp[n]来表示动态规划表，dp[i],i>0,i<=n,表示到达i级台阶的方法数。

迭代法（自顶向下） 

1
2
3
4
5
6
7
8
9
10
11
/*dp是全局数组，大小为n,全部初始化为0，是题目中的动态规划表*/
int fun(int n){
	if (n==1||n==2)
		return n;
	/*判断n-1的状态有没有被计算过*/
	if (!dp[n-1])
		dp[n-1] = fun(n-1);
	if(!dp[n-2])
		dp[n-2]=fun(n-2);
	return dp[n-1]+dp[n-2];
}

LeetCode相关问题： leetcode问题 解法

动态规划求解（自底向上）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int getClimbingWays(int n, HashMap<Integer, Integer> map){
    if(n<1){
        return 0;
    }
    if(n==1){
        return 1;
    }
    if(n==2){
        return 2;
    }
    int a = 1;
    int b = 2;
    int tmp = 0;
    
    for (int i = 3; i<=n; i++){
        tmp = a + b;
        a = b;
        b = tmp;
    }
    return tmp;
}

例题二：国王与金矿（与01背包问题类似）

有一个国家发现了5座金矿，每座金矿的黄金储量不同，需要参与挖掘的工人数也不同。参与挖矿工人的总数是10人。每座金矿要么全挖，要么不挖，不能派出一半人挖取一半金矿。要求用程序求解出，要想得到尽可能多的黄金，应该选择挖取哪几座金矿？

500金/5人；200金/3人；300金/4人；350金/3人；400金/5人

问题的状态转移方程式：

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]) //最后一个矿有选择不挖和挖两个选择，在其中选最优的选择

排列组合

每一座金矿都有挖与不挖两种选择，如果有N座金矿，排列组合起来就有2N种选择。对所有可能性做遍历，排除那些使用工人数超过10的选择，在剩下的选择里找出获得金币数最多的选择。（O(2N)）

简单递归

把状态转移方程式翻译成递归程序，递归的结束的条件就是方程式当中的边界。因为每个状态有两个最优子结构，所以递归的执行流程类似于一颗高度为N的二叉树。方法的时间复杂度是O(2^N)。

备忘录算法

在简单递归的基础上增加一个HashMap备忘录，用来存储中间结果。HashMap的Key是一个包含金矿数N和工人数W的对象，Value是最优选择获得的黄金数。方法的时间复杂度和空间复杂度相同，都等同于备忘录中不同Key的数量。

动态规划

计算过程，除了第一行以外，每个格子都是由前一行的一个或者两个格子推导而来 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
int getMostGold(int n, int w, int[] g, int[] p){
    int[] preResults = new int[p.length];
    int[] results = new int[p.length];
    //填充边界格子的值
    for(int i=0; i<=n; i++){
        if(i < p[0]){
            preResults[i] = 0;
        }else{
            preResults[i] = g[0];
        }
    }
    //填充其余格子的值，外层循环是金矿数量，内层循环是工人数
    for(int i=0; i<=n; i++){
        for(int j=0;j<=w;j++){
            if(j < p[i]){
                results[j]=preResults[j]; //这里代码有问题，java中数组不能直接赋值，可改用clone方式赋值
            }else{
                results[j]=Math.max(preResults[j],preResults[j-p[i]]+g[i]);
            }
        }
        preResults = results;
    }
    return preResults[n];
}

方法的时间复杂度是 O(n * w)，空间复杂度是(w)。需要注意的是，当金矿只有5座的时候，动态规划的性能优势还没有体现出来。当金矿有10座，甚至更多的时候，动态规划就明显具备了优势。由于动态规划方法的时间和空间都和W成正比，而简单递归却和W无关，所以当工人数量很多的时候，动态规划反而不如递归。

例题三：最长公共子序列

如果字符串一的所有字符按其在字符串中的顺序出现在另外一个字符串二中， 则字符串一称之为字符串二的子串。

注意，并不要求子串（字符串一）的字符必须连续出现在字符串二中。 请编写一个函数，输入两个字符串，求它们的最长公共子串，并打印出最长公共子串。 例如：输入两个字符串BDCABA和ABCBDAB，字符串BCBA和BDAB都是是它们的最长公共子串， 则输出它们的长度4，并打印任意一个子串。

LCS问题具有重叠子问题的性质，因此有些子问题可通过“查表”而直接得到。

用二维数组c[i][j]记录串x1x2⋯xi与y1y2⋯yj的LCS长度，则可得到状态转移方程 状态转移方程

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public class LCSequence {
    //求解str1 和 str2 的最长公共子序列
    public static int LCS(String str1, String str2){
        int[][] c = new int[str1.length() + 1][str2.length() + 1];
		//初始化
        for(int row = 0; row <= str1.length(); row++)
            c[row][0] = 0;
        for(int column = 0; column <= str2.length(); column++)
            c[0][column] = 0;
        
        for(int i = 1; i <= str1.length(); i++)
            for(int j = 1; j <= str2.length(); j++)
            {
                if(str1.charAt(i-1) == str2.charAt(j-1))
                    c[i][j] = c[i-1][j-1] + 1;
                else if(c[i][j-1] > c[i-1][j])
                    c[i][j] = c[i][j-1];
                else
                    c[i][j] = c[i-1][j];
            }
        return c[str1.length()][str2.length()];
    }
}

Reference：

  1. http://www.cnblogs.com/steven_oyj/archive/2010/05/22/1741374.html
  2. http://www.cnblogs.com/pengyingh/articles/2396427.html
  3. https://www.sohu.com/a/153858619_466939
  4. https://www.cnblogs.com/hapjin/p/5572483.html