动态规划

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 发布!

你可能感兴趣的