f(Program,Poet)=Programet

5.动态规划
a.另一种形式的工程计划
b.记忆化搜索
c.数字三角形：递推地思考问题
d.石子合并：状态的确定
e.街道问题：状态量维数的确定与无后效性
f.0-1背包：巧妙地选取状态量
g.Bitonic旅行：最佳的状态转化方式
h.最长非降子序列模型
i.构造动态规划算法
j.动态规划、递推、广度优先搜索的区别与转化

a.另一种形式的工程计划

上一章我们讲过，若工程计划问题中某一步权值只和上一步或少数几步的选择有关，我们可以使用效率较高的动态规划算法。
看下面这个问题：

  4-9
 /   \
1-2-5-3-1
 \ \ / /
  1-7-8

上图的数字间连了线。现要从最左边的“1”走到最右边的“1”，每次都只能沿线向右走到右边一列的某个数上，要求找出一条路径，路径上的五个数之和最大。
当然我们可以把这理解为工程计划问题的一种形式。
这里，每一步的选择与上一步相关；似乎也与前面几步的选择有关，但是注意，前几步的影响都可以表现在上一步上，上一步方法的选择已经可以独立决定这一步每种选择的权值。此处适用动态规划。
换句“专业”点的话，这里满足“无后效性原则”，即之后过程不受之前具体过程的影响。这在后面会具体说明。

b.记忆化搜索

再讲动态规划之前，我们先接触一下记忆化搜索。
注意到，在深度优先搜索中，用于递归的函数cal(…)有时会被用同样的参数调用多次。你可能很容易想到，如果在第一次调用时把参数和对应的函数值储存起来，若以后再以同样的参数调用，就不用执行递归函数，直接取出所得的值，不是快得多？
如果你能想到这些，你就已经学会记忆化搜索了。

事实上，记忆化搜索能大幅提高效率的地方，往往是在动态规划的题目中。
动态规划能解决的问题，往往可以用记忆化搜索替代动态规划解决。如果你实在无法掌握动态规划，你可以选择使用记忆化搜索。不过你要注意以下事实：
动态规划程序实现较容易，程序段短，便于调试；记忆化搜索实现就比较繁琐。
虽然记忆化搜索可以把时间复杂度降低到动态规划的水平，但是实际执行时间会大于动态规划，甚至有几倍到十几倍的差距。

这里不给出记忆化搜索的代码了。我们还是首选动态规划吧～

c.数字三角形：递推地思考问题

上一章中我们讲过数字三角形问题：
有一个数字三角形（如下图）。现有一只蚂蚁从顶层开始向下走，每走下一级时，可向左下方向或右下方向走。求走到底层后它所经过的数的最大值。

    1
   6 3
  8 2 6
 2 1 6 5
3 2 4 7 6

对于这个问题，贪心法得不到最优解，搜索法效率太低。我们知道，深度优先搜索利用了递归式的思维，动态规划中，我们使用递推式的思维。
递归：要知道第五层时的最大值，就要知道第四层时的最大值；要知道第四层时的最大值，就要知道第三层时的最大值……而每一步推导的方法是相似的。
递推：知道第一层的最大值，就能知道第二层的最大值，也就能知道第三层的最大值……而每一步推导的方法是相似的。
对比之下，递推思维不是从结论入手的，有时容易失去方向；但是有时却可以有很高的效率。
动态规划和普通递推的区别在于动态规划需要在每一步作比较、取最优值。

对于数字三角形问题，我们可以这样思考：设二维数组A[i][j]，表示走到第i行的第j个数时所经过的数字和的最大值。例如对图中三角形，A[3][2]=max{1+6+2,1+3+2}。
这样，我们又可以得到递推关系A[i][j]=p[i][j]+max{A[i-1][j-1],A[i-1][j]}（实现时注意A[i-1][j-1]或A[i-1][j]不存在时的处理），其中p[i][j]表示第i行的第j个数的数值。
此外，我们还需要一些初始值：p[i][j]（输入），A[1][1]=p[1][1]。
最终我们可以求出A[5][j]，结论自然是max{A[5][j]}啦～
分析这个算法，若层数大于5，则时间复杂度为O(n^2)。若用搜索，时间复杂度为O(2^n)。显然动态规划效率高很多。

为了更清楚地说明动态规划算法，我们先引入一些概念。
阶段——我们把问题划分为几步，在动态规划中，这叫做“划分阶段”。数字三角形中，每一层可看作是一个阶段。
状态——每一阶段有多种选择，不同的选择会有不同的结果，我们把每阶段的不同情形叫做“状态”。每一阶段包括多个状态。数字三角形中，表示走到第j个数时所经过的数字和的最大值的变量叫做状态。
动态转移方程——我们可以用一个递推式表示某阶段到下一阶段的递推关系，这个递推式叫做动态转移方程。动态转移方程一般含有max{}或min{}。
决策——即对方法的选择。每个阶段都有一个决策。这样的选择是有范围的，这个范围叫做“决策允许集合”。
策略——一套完整的决策的组合。“最优策略”即最佳的决策组成的策略。
还有一些概念因为使用较少，这里不再详细介绍。

注意可以运用动态规划解决的问题的两个必需特性：
最优化原理——简单地说，最优策略某几个连续阶段上的决策组合，也是这几个阶段组成的子问题的最优策略。
无后效性原则——某阶段以后的决策，与该阶段之前的具体决策无关，只与该阶段的状态有关。
注意，有些时候我们认为不满足这两点的问题，换个角度看又是满足的。这正是动态规划的难点。接下来我们就是要寻找合适的角度，找出满足这两个关系的算法。

d.石子合并：状态的确定

用动态规划解决问题，首要也是最重要的步骤就是划分阶段、确定状态。这决定了是否能成功运用动态规划方法。因此。确定一个可行的递推思路是成功的关键。
在这一过程中，要善于变通。

石子合并：N堆石子围成一圈，每堆石子的量a[i]已知。每次可以将相邻两堆合并为一堆，将合并后石子的总量记为这次合并的得分。N-1次合并后石子成为一堆。求这N-1次合并的得分之和可能的最大值。
数据规模：N≤100，a[i]≤20000000
算法构造：
分析数据规模——算法可承受的最大数据规模O(N^3)，搜索必然超时，贪心可承受数据规模太大，优先考虑动态规划。
递推思路——计算将第i堆至第j堆完全合并所能获得的最大得分。这是此题的关键。考虑模拟每种合并后的具体情形是行不通的。把问题变成这样后就好解决了。
划分阶段——以合并的次数作为标准划分阶段。
确定状态——第i堆至第j堆合并所能获得的最大价值。
状态转移方程——f(i,j)=max{f(i,k)+f(k+1,j)},0<i≤k<j≤n
边界状态——f(i,i)=a[i]
分析知时间复杂度为O(n^3)，满足要求。
递推求出f(1,n)即可。动态规划特点是“思路难，实现易”，这里不再给出源代码。

另外，NOIP2006出现了一道石子合并的衍生问题。
在Mars星球上，每个Mars人都随身佩带着一串能量项链。在项链上有N颗能量珠。能量珠是一颗有头标记与尾标记的珠子，这些标记对应着某个正整数。并且，对于相邻的两颗珠子，前一颗珠子的尾标记一定等于后一颗珠子的头标记。因为只有这样，通过吸盘（吸盘是Mars人吸收能量的一种器官）的作用，这两颗珠子才能聚合成一颗珠子，同时释放出可以被吸盘吸收的能量。如果前一颗能量珠的头标记为m，尾标记为r，后一颗能量珠的头标记为r，尾标记为n，则聚合后释放的能量为（Mars单位），新产生的珠子的头标记为m，尾标记为n。
需要时，Mars人就用吸盘夹住相邻的两颗珠子，通过聚合得到能量，直到项链上只剩下一颗珠子为止。显然，不同的聚合顺序得到的总能量是不同的，请你设计一个聚合顺序，使一串项链释放出的总能量最大。
建议读者自己思考解决，以熟悉动态规划的思维过程。在附件中给出解法的源代码。

e.街道问题：状态量维数的确定与无后效性

下面是动态规划的经典问题之一：街道问题。
下图表示一个街道。现有类似这样的N*N的街道，且每段路有一个权值。现在要从左上角沿线走到右下角，每次只能向右或向下走。求经过路段权值和的最大值。
数据规模：N≤1000

   3   2   5   6
 ┌─┬─┬─┬─┐
4│  3   7   2   8
 ├7-┼5-┼1-┼6-┤
2│  3   6   8   2
 ├3-┼1-┼2-┼9-┤
6│  8   5   1   4
 ├4-┼5-┼9-┼8-┤
9│  3   2   8   1
 └6-┴4-┴4-┴2-┘

分析数据规模——算法可承受的最大数据规模O(N^2)，搜索必然超时，贪心可承受数据规模太大，优先考虑动态规划。
递推思路——从左上角向右下角推，求出走到每一点所经过权值和的最大值。
划分阶段——按斜向(／)划分
剩下的读者自己思考。时间复杂度应为O(n^2)。

上面问题中，若是改为从左上角沿线走到右下角再以不交叉的线路返回到出发点，算法应该做怎样的修改？
原来的状态已经不能保证“不交叉”，在这种状况下，我们用增加一维状态量的方法，以讨论是否交叉，
比较方便的思路——从左上角出发两条路，再向右下方递推的过程中，两条路的最末端始终不能是同一点，必须分布在这一阶段的两点上，直到最后在右下角汇合。
由于增加了一维状态量，时间复杂度变为O(n^3)。

f.0-1背包：巧妙地选取状态量

有时，选定状态时发现不能使用动态规划，或问题从表面上看让人无所适从，我们不妨从另一个角度看问题。

上一章我们介绍了部分背包问题，下面我们介绍更经典的0-1背包问题。
问题描述：有N件物品和一个最大载重为M的背包，每件物品都有相应的重量和价值。现要求给出一个存放方案，使背包中物品总价值最大。所涉及到的数字均为整数。
数据规模：1≤N≤100，1≤M≤10000。
这个问题与部分背包问题的区别在于，物品只能整件放入，不能只取一部分。这样，背包很可能会有部分载重量未利用。若用贪心法取单位重量价值高的，可能会使背包未利用的载重升高，得不到最优方案。
考虑到数据规模，选用动态规划法。
似乎只有“每考虑一件物品为一阶段”的划分方法。可是如何确定状态？很多人想不到这个方法：以一个最大载重值为一个状态。
完整递推思路——计算将考虑了前i个物品后，最大载重为j的背包能取得的最大价值f(i,j)，这个过程是可由f(i-1,j)和f(i-1,j-g[i])递推而得。最后求出f(N,M)。
动态转移方程——f(i,j)=max{f(i-1,j),f(i-1,j-g[i])+v[i]},1≤i≤N,1≤j≤M（实现时注意对边界情形的处理），其中g[i]、v[i]分别表示第i件物品的重量、价值。
时间复杂度为O(N*M)，可以接受。
实现时要注意空间复杂度（N*M的数组显然是开不出来的）。

动态规划的空间消耗是很大的，往往比深度优先搜索大得多。
动态规划的算法，往往空间复杂度比时间复杂度少一维。
下面是常见的一种降低储存的方法（在第二章提到过）——
动态规划实现时往往可表示成矩阵形式。若递推矩阵中每一行的值只与上一行有关，输出只和最末行有关，则可将奇数行储存在第一行，偶数行储存在第二行，降低空间复杂度。
这里还有一种优化方法2——
若递推矩阵中每一行中某一列的值只与上一行中这一列及位于其右的列的有关，输出只和最末行有关，则可按从左到右的顺序计算该行每一列的值，并覆盖掉原值即可。

上面的0-1背包问题，实现时，面临的情况与“优化方法2”中的类似但又有区别——每一行中某一列的值只与上一行中这一列及位于其左的列的有关。这样，我们需要按从右到左的顺序计算。空间复杂度O(M)。
附件中给出0-1背包问题的源代码。

背包问题还有两种。
一种是完全背包问题：在0-1背包的基础上，每种物品可放入很多个。这个问题也用动态规划法解决。你会发现，这个问题实现时只与0-1背包差一点点——它按从左到右的顺序计算，而0-1背包按从右到左的顺序计算。
另一种有时也称作完全背包问题：在0-1背包的基础上，要求背包恰好达到载重。这个问题留给读者思考。

g.Bitonic旅行：最佳的状态转化方式

历史上有一个著名的“货郎担问题”（也叫“中国邮路问题”）：已知n个点两两间的距离，给出过这些定点的最短闭合回路。（有时把这n个定点间距离定义为欧氏几何平面上距离，称“欧几里德旅行商问题”。）
这个问题是NP-难问题，只能用搜索解决。
后来，J. L. Bentley提出了这个问题的变形——Bitonic Tour问题（又称双调旅程问题）。
Bitonic旅行：已知地图上n个旅行须到达的城市，要求从最西端的城市开始，严格地由西向东到最东端的城市，再严格地由东向西回到出发点，除出发点外每个城市经过且只经过一次。给出路程的最短值。
数据规模：1≤n≤1000
你可能会这么想：按旅行顺序每过一个城市为一阶段。可是这样，状态量需要记录由东向西每一步所经过的城市，时间复杂度O(2^n)，与搜索无异！
我们需要换一种状态转化方式。
递推思路——从最东端开始，找两条到最西端的路径。将地点按从东到西编号，每加入一个地点为一个阶段。计算从地点i到最东再到地点j路程的最小值f(i,j)，这个过程是递推的。最后求出min{f(n,k)+dist[n,k]}。
动态转移方程——
f(i,j)=f(i-1,j)+dist[i,i-1],1≤j≤i-2,i≤n
f(i,j)=f(i,j-1)+dist[j,j-1],1≤j=i-1,i≤n
（实现时注意对边界情形的处理），其中dist[i,j]表示i与j间距离。
时间复杂度为O(n^2)，很好。附件中给出源代码。

h.最长非降子序列模型

NOIP命题者还是比较仁慈的，考察动态规划时降低了难度，大多考察“模仿”，很少“构造”——NOIP的动态规划题，很多都是在经典问题基础上略作变化而成。下面这个问题是我接触到的变形题最泛滥的经典问题。

最长非降子序列：给定一串数，从中删去一些数，使剩下的序列是非降的。求剩下的序列的最大长度。
数据规模：1≤n≤1000
递推思路——f(i)表示对于前i个数组成的序列，保留第i个数时能取得的非降子序列的最大长度。
动态转移方程——f(i)=max{f(j)+1},n[j]≤n[i],1≤j<i（实现时注意对边界情形的处理），其中n[i]表示序列中第i个数的值。
时间复杂度为O(n^2)。
说明：实际上最长非降子序列的最佳解法是二分法（但NOIP要求的数据规模较小，往往可以用动态规划解）。最长非降子序列的二分法会在第七章介绍。

看看下面这两个问题，你是不是觉得一下子就有了思路？
合唱队形（NOIP2004）——N位同学站成一排，音乐老师要请其中的(N-K)位同学出列，使得剩下的K位同学排成合唱队形。合唱队形是指这样的一种队形：设K位同学从左到右依次编号为1，2…，K，他们的身高分别为T1，T2，…，TK，则他们的身高满足T1<...Ti+1>…>TK(1<=i<=K)。你的任务是，已知所有N位同学的身高，计算最少需要几位同学出列，可以使得剩下的同学排成合唱队形。2≤N≤100，130≤Ti≤230。
船（摘自《奥赛经典》）——PALMIA国家被一条河流分成南北两岸，南北两岸上各有N个村庄。北岸的每一个村庄有一个唯一的朋友在南岸，且他们的朋友村庄彼此不同。每一对朋友村庄想要一条船来连接他们，他们向政府提出申请以获得批准。由于河面上常常有雾，政府决定禁止船只航线相交（如果相交，则很可能导致碰船）。你的任务是编写一个程序，帮助政府官员决定批准哪些船只航线，使得不相交的航线数目最大。1≤N≤5000。

对于“合唱队形”，我们只需讨论第i人作最高点时，左边升、右边降序列长度最大值。时间复杂度为O(n^3)。
对于“船”，我们记a[i]为北岸第i村对应的南岸村庄的位置，这个问题就变成了求a[i]最长非降子序列的问题。这里最好使用二分法解答。（请读者好好想想这是为什么。）

可见，一个问题可以衍生出很多类似的问题。要抓好经典问题的解决策略，这在NOIP中大有用处。

i.构造动态规划算法

不过，少数时候经典算法是帮不上忙的，我们自己要依据动态规划原理，动脑子构造算法。
有一些小技巧：
1.抓住“递推”这一本质，理清思路。
2.如果你对自己的数学相当有自信，你可以尝试数学推导动态转移方程。
3.有时，构造需要一些反常规的思维，可以试着摆脱常规思路的束缚，或者借鉴一下经典算法是如何打破思维局限的。
4.分析数据规模，如果有更简单的满足数据规模要求的算法，不必强求动归；适用动归的数据规模一般是30至1000。

j.动态规划、递推、广度优先搜索的区别与转化

动态规划是递推思想的典型应用。广度优先搜索有时也会用到递推思想。
有时，我们会用递推的方法来分析问题、尝试归纳问题。这通常会把我们引向动态规划或广度优先搜索。我们往往并不需要在开始时决定使用动态规划还是广度优先搜索，而是先理清递推思路。
更深入地说，动态规划可看作是对图的一种遍历；在这种遍历中，后扩展的节点的当前值不会影响先扩展的节点的当前值。这就是它与广度优先搜索的区别所在——广度优先搜索中，后扩展的节点的当前值会影响先扩展的节点的当前值。

动态规划越来越被NOIP提高组命题者青睐，成为每年必考点。动归思考难度大，而实现较容易，这需要我们多看经典问题，积累经验。

习题
动态规划的习题 ——感谢 深蓝评测系统 提供习题

附件：能量项链、0-1背包、Bitonic旅行解法源文件
抱歉，只有对本站任何文章发表过评论才能阅读隐藏内容。
未提及的经典动态规划问题（点击这里查看）字符串比较问题 给出的链接会链接到 csdn

本文由 最后的叶子 创作，转载或引用前请联系我们。

相关文章：

1. NOIP实用算法 目录
2. NOIP实用算法 1.模拟方法
3. NOIP实用算法 2.排序算法与算法时空复杂度
4. NOIP实用算法 6.常用数学方法
5. NOIP实用算法 3.搜索

2009年8月14日 星期五