动态规划

jiezi

5 年前

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

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

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

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

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

记住求解的方式有两种

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

为了说明动态规划的这两种方法，举一个最经典的例子：求斐波拉契数列 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

创建一个 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]中。

备忘录法还是利用了递归，其实并非正宗的 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 了。动态规划远远不止如此，下面先给出一个例子看看能否独立完成。然后再对动态规划的其他特性进行分析。

来自于算法导论

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

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

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

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

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

开始总结方法论吧!

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

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

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

在斐波拉契数列和钢条切割结构图中，可以看到大量的重叠子问题，比如说在求 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 发布！

动态规划

1 可信宣言

2 核心思想

2 两种形式

递归算法的执行流程

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

2.2 自底向上的动态规划

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

递归版本

备忘录版本

自底向上的动态规划

4 DP 的原理

4.1 最优子结构

4.2 重叠子问题

总结

参考