共计 4416 个字符,预计需要花费 12 分钟才能阅读完成。
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 发布!