规划方程：fk(sk)?maxfk?1(sk?uk)?Datak(sk)
uk?0,1边界条件：fk(0)?0fk(k?1)?0(0?k?总行数)
这是一个比较简单的最优化问题，我们还可以把这个问题改成一个更加简单的整数统计问题：求顶点到每一点的路径总数。把这个总数用fk(sk)表示，那么递推公式就是：
1fk(sk)??uk?0fk?1(sk?uk)
在这里，虽然求和公式只有两项，但我们仍然用∑的形式表示，就是为了突出这个递推公式和上面的规划方程的相似之处。这两个公式的边界条件都是一模一样的。 再回到我们上面的“钉子与小球”问题，这是一个概率统计问题。我们继续沿用上面的思想，用fk(sk)表示小球落到第k行第sk个钉子上的概率，则递推公式如下：
1fk(sk)??uk?0fk?1(sk?uk)?Exist2k?1(sk?uk)?fk?2(sk?1)?(1?Existk?2(sk?1))
（这里函数Existk(sk)表示第k行第sk个钉子是否存在，存在则取1，不存在则取0）
边界条件
f1(1)?1fk(0)?0fk(k?1)?0(1?k?总行数)
可以看出这个公式较之上面的两个式子虽然略有变化，但是其基本思想还是类似的。在解这个问题的过程中，我们再次运用了动态规划的思想。
一般说来，很多最优化问题都有着对应的计数问题；反过来，很多计数问题也有着对应的最优化问题。因此，我们在遇到这两类问题时，不妨多联系、多发展，举一反三，从比较中更深入地理解动态规划的思想。
其实递推和动态规划这两种方法的思想本来就很相似，也不必说是谁借用了谁的思想。关键在于我们要掌握这种思想，这样我们无论在用动态规划法解最优化问题，或是在用递推法解判定型、计数问题时，都能得心应手、游刃有余了。
§3.2动态规划与搜索
——动态规划是高效率、高消费算法
同样是解决最优化问题，有的题目我们采用动态规划，而有的题目我们则需要用搜索。这其中有没有什么规则呢？
我们知道，撇开时空效率的因素不谈，在解决最优化问题的算法中，搜索可以说是“万能”的。所以动态规划可以解决的问题，搜索也一定可以解决。
把一个动态规划算法改写成搜索是非常方便的，状态转移方程、规划方程以及边界条件都可以直接“移植”，所不同的只是求解顺序。动态规划是自底向上的递推求
第 11 页 共 29页
解，而搜索则是自顶向下的递归求解（这里指深度搜索，宽度搜索类似）。
反过来，我们也可以把搜索算法改写成动态规划。状态空间搜索实际上是对隐式图中的点进行枚举，这种枚举是自顶向下的。如果把枚举的顺序反过来，变成自底向上，那么就成了动态规划。（当然这里有个条件，即隐式图中的点是可排序的，详见下一节。） 正因为动态规划和搜索有着求解顺序上的不同，这也造成了它们时间效率上的差别。在搜索中，往往会出现下面的情况：
A1 B1 C1 C2 B2 C3 C1 B1 C2 C2 A1 B2 C3 C1 B1 C2 A1 B2 C3 (a) (b) (c)
对于上图(a)这样几个状态构成的一个隐式图，用搜索算法就会出现重复，如上图(b)所示，状态C2被搜索了两次。在深度搜索中，这样的重复会引起以C2为根整个的整个子搜索树的重复搜索；在宽度搜索中，虽然这样的重复可以立即被排除，但是其时间代价也是不小的。而动态规划就没有这个问题，如上图(c)所示。
一般说来，动态规划算法在时间效率上的优势是搜索无法比拟的。（当然对于某些题目，根本不会出现状态的重复，这样搜索和动态规划的速度就没有差别了。）而从理论上讲，任何拓扑有序（现实中这个条件常常可以满足）的隐式图中的搜索算法都可以改写成动态规划。但事实上，在很多情况下我们仍然不得不采用搜索算法。那么，动态规划算法在实现上还有什么障碍吗？
A1 B1 C1 C2 B2 C3 B1 C2 C2 A1 B2 C1 B1 C2 A1 B2 C3 (a) (b) (c)
考虑上图(a)所示的隐式图，其中存在两个从初始状态无法达到的状态。在搜索算法中，这样的两个状态就不被考虑了，如上图(b)所示。但是动态规划由于是自底向上求解，所以就无法估计到这一点，因而遍历了全部的状态，如上图(c)所示。 一般说来，动态规划总要遍历所有的状态，而搜索可以排除一些无效状态。更重要的事搜索还可以剪枝，可能剪去大量不必要的状态，因此在空间开销上往往比动态规划要低很多。
如何协调好动态规划的高效率与高消费之间的矛盾呢？有一种折衷的办法就是记忆化算法。记忆化算法在求解的时候还是按着自顶向下的顺序，但是每求解一个状态，就将它的解保存下来，以后再次遇到这个状态的时候，就不必重新求解了。这种方法综合了搜索和动态规划两方面的优点，因而还是很有实用价值的。
第 12 页 共 29页
§3.3动态规划与网络流
——动态规划是易设计易实现算法
由于图的关系复杂而无序，一般难以呈现阶段特征（除了特殊的图如多段图，或特殊的分段方法如Floyd），因此动态规划在图论中的应用不多。但有一类图，它的点却是有序的，这就是有向无环图。
在有向无环图中，我们可以对点进行拓扑排序，使其体现出有序的特征，从而据此划分阶段。在有向无还图中求最短路径的算法[4]，已经体现出了简单的动态规划思想。但动态规划在图论中还有更有价值的应用。下面先看一个例子。
[例6] N个人的街道问题：在街道问题（参见例3）中，若有N个人要从左下角走
向右上角，要求他们走过的边的总长度最大。当然，这里每个人也只能向右或向上走。下面是一个样例，左图是从出发地到目的地的三条路径，右图是他们所走过的边，这些边的总长度为5 + 4 + 3 + 6 + 3 + 3 + 5 + 8 + 8 + 7 + 4 + 5 + 9 + 5 + 3 = 78（不一定是最大）。
3 7 4 8 7 6 3 5 3 4 6 3 5 2 8 5 9 4 3 6 3 5 8 7 4 3 7 5 4 6 2 3 7 4 8 7 6 3 5 3 4 6 3 5 2 8 5 9 4 3 6 3 5 8 7 4 3 7 5 4 6 2 这个题目是对街道问题的又一次扩展。仿照街道问题的解题方法，我们仍然可以用动态规划来解决本题。不过这一次是N个人同时走，状态变量也就需要用N维来表示，。相应的，决策变量也要变成N维，uk=(uk,1,uk,2,…,uk,N)。状态转移方程不需要做什么改动：
??sk?1,i?sk,i?1?uk,i???sk?1,i?sk,i?uk,i(k?row)(k?row)(1?i?N)
在写规划方程时，需要注意在第k阶段，N条路径所走过的边的总长度的计算，
在这里我就用gk(sk,uk)来表示了：
fk(sk)?maxuk,i?0,1(1?i?N)?fk?1?Tk(sk,uk)??gk(sk,uk)?
边界条件为f1?(1,1,?,1)??0
可见将原来的动态规划算法移植到这个问题上来，在理论上还是完全可行的。但是，现在的这个动态规划算法的时空复杂度已经是关于N的指数函数，只要N稍微大一点，这个算法就不可能实现了。
下面我们换一个思路，将N条路径看成是网络中一个流量为N的流，这样求解的目标就是使这个流的费用最大。但是本题又不同于一般的费用流问题，在每一条边e
第 13 页 共 29页
上的流费用并不是流量和边权的乘积f(e)?w(e)，而是用下式计算：
?w(e)??0f(e)?0f(e)?0
为了使经典的费用流算法适用于本题，我们需要将模型稍微转化一下：
w0 c1=1 w1=w0 c2=∞ w2=0 如图，将每条边拆成两条。拆开后一条边上有权，但是容量限制为1；另一条边没有容量限制，但是流过这条边就不能计算费用了。这样我们就把问题转化成了一个标准的最大费用固定流问题。
这个算法可以套用经典的最小费用最大流算法，在此就不细说了。（参见附录中的源程序）
这个例题是我仿照IOI97的“障碍物探测器”一题[6]编出来的。“障碍物探测器”比这一题要复杂一些，但是基本思想是相似的。类似的题目还有99年冬令营的“迷宫改造”[7]。从这些题目中都可以看到动态规划和网络流的联系。
推广到一般情况，任何有向无环图中的费用流问题在理论上说，都可以用动态规划来解决。对于流量为N（如果流量不固定，这个N需要事先求出来）的费用流问题，用N维的变量sk=(sk,1,sk,2,…,sk,N)来描述状态，其中sk,i?V(1?i?N)。相应的，决策也用N维的变量uk=(uk,1,uk,2,…,uk,N)来表示，其中uk,i?E(sk,i)(1?i?N)，E(v)表示指向v的弧集。则状态转移方程可以这样表示：
sk-1,i = uk,i的弧尾结点
??fk?Tk(sk,uk)??f(s)?opt规划方程为kk?uk,i?E(sk,i)??w(u) ?k??i?1?N边界条件为f1?(1,1,?1)??0
但是，由于动态规划算法是指数级算法，因而在实现中的局限性很大，仅可用于
一些N非常小的题目。然而在竞赛解题中，比如上面说到的IOI97以及99冬令营测试时，我们使用动态规划的倾向性很明显（“障碍物探测器”中，我们用的是贪心策
[8]
略，求N=1或N=2时的局部最优解）。这主要有两个原因：
一．虽然网络流有着经典的算法，但是在竞赛中不可能出现经典的问题。如果要
运用网络流算法，则需要经过一番模型转化，有时这个转化还是相当困难的。因此在算法的设计上，灵活巧妙的动态规划算法反而要更为简单一些。 二．网络流算法实现起来很繁，这是被人们公认的。因而在竞赛的紧张环境中，
实现起来有一定模式的动态规划算法又多了一层优势。 正由于动态规划算法在设计和实现上的简便性，所以在N不太大时，也就是在动
第 14 页 共 29页
态规划可行的情况下，我们还是应该尽量运用动态规划。
§4结语
本文的内容比较杂，是我几年来对动态规划的参悟理解、心得体会。虽然主要的篇幅讲的都是理论，但是根本的目的还是指导实践。
动态规划，据我认为，是当今信息学竞赛中最灵活、也最能体现解题者水平的一类解题方法。本文内容虽多，不能涵盖动态规划之万一。“纸上得来终觉浅，绝知此事要躬行。”要想真正领悟、理解动态规划的思想，掌握动态规划的解题技巧，还需要在实践中不断地挖掘、探索。实践得多了，也就能体会到渐入佳境之妙了。
动态规划， 算法之常， 运用之妙， 存乎一心。
【附录：部分试题与源程序】
1. “花店橱窗布置问题”试题 LITTLE SHOP OF FLOWERS
PROBLEM
You want to arrange the window of your flower shop in a most pleasant way. You have F bunches of flowers, each being of a different kind, and at least as many vases ordered in a row. The vases are glued onto the shelf and are numbered consecutively 1 through V, where V is the number of vases, from left to right so that the vase 1 is the leftmost, and the vase V is the rightmost vase. The bunches are moveable and are uniquely identified by integers between 1 and F. These id-numbers have a significance: They determine the required order of appearance of the flower bunches in the row of vases so that the bunch i must be in a vase to the left of the vase containing bunch j whenever i < j. Suppose, for example, you have bunch of azaleas (id-number=1), a bunch of begonias (id-number=2) and a bunch of carnations (id-number=3). Now, all the bunches must be put into the vases keeping their id-numbers in order. The bunch of azaleas must be in a vase to the left of begonias, and the bunch of begonias must be in a vase to the left of carnations. If there are more vases than bunches of flowers then the excess will be left empty. A vase can hold only one bunch of flowers.
Each vase has a distinct characteristic (just like flowers do). Hence, putting a bunch of flowers in a vase results in a certain aesthetic value, expressed by an integer. The aesthetic values are presented in a table as shown below. Leaving a vase empty has an aesthetic value of 0.
VASES 1 2 3 4 5 第 15 页 共 29页