1 可信宣言

最近公司的可信考试认证如火如荼,大众纷纷开始了刷题的痛快之旅
在字符串题目中, 有关动态规划（Dynamic Programming）算法(y以下简称DP)的题目很多
对于工作级别认证的我来说，不管是算法还是OJ里面遇到的问题里面感觉最难的也就是DP
查找了相关的文献和资料, 准备攻破DP

2 核心思想

A * "1+1+1+1+1+1+1+1 =？" *

A : "上面等式的值是多少"
B : *计算* "8!"

A *在上面等式的左边写上 "1+" *
A : "此时等式的值为多少"
B : *quickly* "9!"
A : "你怎么这么快就知道答案了"
A : "只要在8的基础上加1就行了"
A : "所以你不用重新计算因为你记住了第一个等式的值为8!动态规划算法也可以说是 
'记住求过的解来节省时间'"

算法的核心就是记住已经解决过的子问题的解

2 两种形式

记住求解的方式有两种

• 自顶向下的备忘录法
• 自底向上

为了说明动态规划的这两种方法，举一个最经典的例子：求斐波拉契数列Fibonacci 。先看一下这个问题：

Fibonacci (n) = 1;   n = 0

Fibonacci (n) = 1;   n = 1

Fibonacci (n) = Fibonacci(n-1) + Fibonacci(n-2)

该算法使用递归十分的简单(但容易超时)
先使用递归版本来实现这个算法：

int fib(int n)
{
    if (n <= 0)
        return 0;
    if (n == 1)
        return 1;
    return fib(n - 1)+fib(n - 2);
}

递归算法的执行流程

假如输入5，那么执行的递归树如下：

上面的递归树中的每一个子节点都会执行一次，于是很多重复的节点被执行，fib(2)被重复执行了4次。
由于调用每一个函数的时候都要保留上下文，所以空间上开销也不小。
这么多的子节点被重复执行，如果在执行的时候把执行过的子节点保存起来，后面要用到的时候直接查hash表的话可以节约大量的时间(空间换时间)。

下面就看看动态规划的两种方法怎样来解决斐波拉契数列Fibonacci 数列问题。

将数组看成是特别的hash表,下标即hash的key,对应数组值即为hash的value

2.1 自顶向下的备忘录法(top-down with memoization)

创建一个 n+1 的数组来保存求出的斐波拉契数列中的每一个值

• 在递归的时候如果发现前面fib（n）的值计算出来了就不再计算
• 如果未计算出来，则计算出来后保存在Memo数组中，下次在调用fib（n）的时候就不会重新递归了。

比如上面的递归树中在计算fib（5）的时候先计算fib（4），调用fib（4）算出了fib（3）后，fib（5）再调用fib（3）就不会再递归fib（3）的子树了，因为fib（3）的值已经保存在Memo[4]中。

2.2 自底向上的动态规划

备忘录法还是利用了递归，其实并非正宗的DP算法
上面算法不管怎样，计算fib（5）的时候最后还是要计算出fib（1），fib（2），fib（3）,递归本身的开销不可避免

何不先直接计算出fib（1），fib（2），fib（3）……,呢？这也就是DP的核心，先计算子问题，再由子问题计算父问题。

自底向上方法也是利用数组保存了先计算的值，为后面的调用服务。
观察参与循环的只有 i，i - 1 , i - 2三项，因此该方法的空间可以进一步的压缩如下。

一般来说由于备忘录方式的动态规划方法使用了递归，递归的时候会产生额外的开销，使用自底向上的动态规划方法要比备忘录方法好。

你以为看懂了上面的例子就懂得了动态规划吗？那就too young too simple了。动态规划远远不止如此，下面先给出一个例子看看能否独立完成。然后再对动态规划的其他特性进行分析。

3 算法导论经典问题 - 钢条切割

• 来自于算法导论

现在使用一下前面讲到三种方法来来实现一下。

递归版本

递归的思路其实和回溯法是一样的，遍历所有解空间但这里和上面斐波拉契数列的不同之处在于，在每一层上都进行了一次最优解的选择，q = max(q, p[i-1] + cut(p, n-i))这个段语句就是最优解选择，这里上一层的最优解与下一层的最优解相关。

备忘录版本

备忘录方法就是在递归的时候记录下已经调用过的子函数的值
这道钢条切割问题的经典之处在于自底向上的动态规划问题的处理，理解了这个也就理解了动态规划的精髓。

自底向上的动态规划

最重要的是理解注释1处的循环，这里
外面的循环是求r[1],r[2]……
里面的循环是求出r[1],r[2]……的最优解
也就是说r[i]中保存的是钢条长度为i时划分的最优解，这里面涉及到了最优子结构问题，也就是一个问题取最优解的时候，它的子问题也一定要取得最优解。

• 下面是长度为4的钢条划分的结构图

4 DP的原理

开始总结方法论吧!

无论是斐波拉契还是钢条切割，都涉及到了重叠子问题和最优子结构。

4.1 最优子结构

第一步就是刻画最优解的结构

如果一个问题的解结构包含其子问题的最优解，就称此问题具有最优子结构性质。
因此，某个问题是否适合应用DP，甄别它是否具有最优子结构是一个极好的切入点。
使用DP时，用子问题的最优解来构造原问题的最优解。
因此必须考查最优解中用到的所有子问题

4.2 重叠子问题

在斐波拉契数列和钢条切割结构图中，可以看到大量的重叠子问题，比如说在求fib（6）的时候，fib（2）被调用了5次，在求cut（4）的时候cut（0）被调用了4次。如果使用递归算法的时候会反复的求解相同的子问题，不停的调用函数，而不是生成新的子问题。如果递归算法反复求解相同的子问题，就称为具有重叠子问题（overlapping subproblems）性质。在动态规划算法中使用数组来保存子问题的解，这样子问题多次求解的时候可以直接查表不用调用函数递归。

动态规划的经典模型
线性模型
线性模型的是动态规划中最常用的模型，上文讲到的钢条切割问题就是经典的线性模型，这里的线性指的是状态的排布是呈线性的。【例题1】是一个经典的面试题，我们将它作为线性模型的敲门砖。

【例题1】在一个夜黑风高的晚上，有n（n <= 50）个小朋友在桥的这边，现在他们需要过桥，但是由于桥很窄，每次只允许不大于两人通过，他们只有一个手电筒，所以每次过桥的两个人需要把手电筒带回来，i号小朋友过桥的时间为T[i]，两个人过桥的总时间为二者中时间长者。问所有小朋友过桥的总时间最短是多少。

每次过桥的时候最多两个人，如果桥这边还有人，那么还得回来一个人（送手电筒），也就是说N个人过桥的次数为2*N-3（倒推，当桥这边只剩两个人时只需要一次，三个人的情况为来回一次后加上两个人的情况…）。有一个人需要来回跑，将手电筒送回来（也许不是同一个人，realy？！）这个回来的时间是没办法省去的，并且回来的次数也是确定的，为N-2，如果是我，我会选择让跑的最快的人来干这件事情，但是我错了…如果总是跑得最快的人跑回来的话，那么他在每次别人过桥的时候一定得跟过去，于是就变成就是很简单的问题了，花费的总时间：

T = minPTime * (N-2) + (totalSum-minPTime)

来看一组数据 四个人过桥花费的时间分别为 1 2 5 10，按照上面的公式答案是19，但是实际答案应该是17。

具体步骤是这样的：

第一步：1和2过去，花费时间2，然后1回来（花费时间1）；

第二歩：3和4过去，花费时间10，然后2回来（花费时间2）；

第三部：1和2过去，花费时间2，总耗时17。

所以之前的贪心想法是不对的。我们先将所有人按花费时间递增进行排序，假设前i个人过河花费的最少时间为opt[i]，那么考虑前i-1个人过河的情况，即河这边还有1个人，河那边有i-1个人，并且这时候手电筒肯定在对岸，所以opt[i] = opt[i-1] + a[1] + a[i] (让花费时间最少的人把手电筒送过来，然后和第i个人一起过河)如果河这边还有两个人，一个是第i号，另外一个无所谓，河那边有i-2个人，并且手电筒肯定在对岸，所以opt[i] = opt[i-2] + a[1] + a[i] + 2*a[2] (让花费时间最少的人把电筒送过来，然后第i个人和另外一个人一起过河，由于花费时间最少的人在这边，所以下一次送手电筒过来的一定是花费次少的，送过来后花费最少的和花费次少的一起过河，解决问题)
所以 opt[i] = min{opt[i-1] + a[1] + a[i] , opt[i-2] + a[1] + a[i] + 2*a[2] }

区间模型
区间模型的状态表示一般为di，表示区间[i, j]上的最优解，然后通过状态转移计算出[i+1, j]或者[i, j+1]上的最优解，逐步扩大区间的范围，最终求得[1, len]的最优解。

【例题2】给定一个长度为n（n <= 1000）的字符串A，求插入最少多少个字符使得它变成一个回文串。
典型的区间模型，回文串拥有很明显的子结构特征，即当字符串X是一个回文串时，在X两边各添加一个字符’a’后，aXa仍然是一个回文串，我们用di来表示A[i…j]这个子串变成回文串所需要添加的最少的字符数，那么对于A[i] == A[j]的情况，很明显有 di = di+1 （这里需要明确一点，当i+1 > j-1时也是有意义的，它代表的是空串，空串也是一个回文串，所以这种情况下di+1 = 0）；当A[i] != A[j]时，我们将它变成更小的子问题求解，我们有两种决策：

1、在A[j]后面添加一个字符A[i]；

2、在A[i]前面添加一个字符A[j]；

根据两种决策列出状态转移方程为：

di = min{ di+1, di } + 1; (每次状态转移，区间长度增加1)

空间复杂度O(n^2)，时间复杂度O(n^2)， 下文会提到将空间复杂度降为O(n)的优化算法。

背包模型
背包问题是动态规划中一个最典型的问题之一。由于网上有非常详尽的背包讲解，这里只将常用部分抽出来。

【例题3】有N种物品（每种物品1件）和一个容量为V的背包。放入第 i 种物品耗费的空间是Ci，得到的价值是Wi。求解将哪些物品装入背包可使价值总和最大。fi表示前i种物品恰好放入一个容量为v的背包可以获得的最大价值。决策为第i个物品在前i-1个物品放置完毕后，是选择放还是不放，状态转移方程为：

fi = max{ fi-1, fi-1 +Wi }

时间复杂度O(VN)，空间复杂度O(VN) （空间复杂度可利用滚动数组进行优化达到O(V) ）。

动态规划题集整理
1、最长单调子序列
Constructing Roads In JG Kingdom★★☆☆☆
Stock Exchange ★★☆☆☆

2、最大M子段和
Max Sum ★☆☆☆☆
最长公共子串 ★★☆☆☆

3、线性模型
Skiing ★☆☆☆☆

总结

弄懂动态规划问题的基本原理和动态规划问题的几个常见的模型，对于解决大部分的问题已经足够了。希望能对大家有所帮助，转载请标明出处http://write.blog.csdn.net/md...，创作实在不容易，这篇博客花了我将近一个星期的时间。

参考

算法导论

本文由博客一文多发平台 OpenWrite 发布！