一．动态规划的逆向思维法
动态规划是一种思维方法，没有统一的、具体的模式。动态规划可以从多方面去考察，不同的方面对动
态规划有不同的表述。我们不打算强加一种统一的表述，而是从多个角度对动态规划的思维方法进行讨
论，希望大家在思维具体问题时，也能够从多个角度展开，这样收获会更大。 逆向思维法是指从问题目标状态出发倒推回初始状态或边界状态的思维方法。如果原问题可以分解成
几个本质相同、规模较小的问题，很自然就会联想到从逆向思维的角度寻求问题的解决。
你也许会想，这种将大问题分解成小问题的思维不就是分治法吗?动态规划是不是分而治之呢?其实，
虽然我们在运用动态规划的逆向思维法和分治法分析问题时，都使用了这种将问题实例归纳为更小的、
相似的子问题，并通过求解子问题产生一个全局最优值的思路，但动态规划不是分治法：关键在于分解
出来的各个子问题的性质不同。
分治法要求各个子问题是独立的(即不包含公共的子问题)，因此一旦递归地求出各个子问题的解后，
便可自下而上地将子问题的解合并成原问题的解。如果各子问题是不独立的，那么分治法就要做许多不
必要的工作，重复地解公共的子问题。
动态规划与分治法的不同之处在于动态规划允许这些子问题不独立(即各子问题可包含公共的子问题)
，它对每个子问题只解一次，并将结果保存起来，避免每次碰到时都要重复计算。这就是动态规划高效
的一个原因。
动态规划的逆向思维法的要点可归纳为以下三个步骤： (1)分析最优值的结构，刻画其结构特征； (2)递归地定义最优值；0
(3)按自底向上或自顶向下记忆化的方式计算最优值。 【例题1】背包问题描述：
有一个负重能力为m的背包和n种物品，第i种物品的价值为v，重量为w。在不超过背包负重能力的前
提下选择若干个物品装入背包，使这些的物品的价值之和最大。每种物品可以不选，也可以选择多个。
假设每种物品都有足够的数量。 分析：
从算法的角度看，解决背包问题一种最简单的方法是枚举所有可能的物品的组合方案并计算这个组合
方案的价值之和，从中找出价值之和最大的方案。显然，这种靠穷举所有可能方案的方法不是一种有效 的算法。
但是这个问题可以使用动态规划加以解决。下面我们用动态规划的逆向思维法来分析这个问题。
(1)背包问题最优值的结构
动态规划的逆向思维法的第一步是刻画一个最优值的结构，如果我们能分析出一个问题的最优值包含
其子问题的最优值，问题的这种性质称为最优子结构。一个问题的最优子结构性质是该问题可以使用动
态规划的显著特征。
对一个负重能力为m的背包，如果我们选择装入一个第 i 种物品，那么原背包问题就转化为负重能力
为 m-w 的子背包问题。原背包问题的最优值包含这个子背包问题的最优值。若我们用背包的负重能力来
划分状态，令状态变量s[k]表示负重能力为k的背包，那么s[m]的值只取决于s[k](k≤m)的值。因此背包
问题具有最优子结构。
(2)递归地定义最优值
动态规划的逆向思维法的第二步是根据各个子问题的最优值来递归地定义原问题的最优值。对背包问
题而言，有状态转移方程：
／max{s[k-w]+v}(其中1≤i≤n，且k-w≥0) s[k]= 若k>0且存在1≤i≤n使k-w≥0， ＼ 0 否则。
有了计算各个子问题的最优值的递归式，我们就可以直接编写对应的程序。下述的函数knapsack是输
入背包的负重能力k，返回对应的子背包问题的最优值s[k]： function knapsack(k:integer):integer； begin
knapsack:=0； for i:=1 to n do if k-w>=0 then begin
t:=knapsack(k-w)+v；
if knapsack < t then knapsack:=t；
end; end；
上述递归算法在求解过程中反复出现了一个子问题，且对每次重复出现的子问题都要重新解一次，这
需要多花费不少时间。下面先考虑一个具体的背包问题。例如，当 m=3，n=2，v[1]=1，w[1]=1，v[2]=2，w[2]=2，
图1示出了由调用knapsack(3)所产生的递归树，每一个结点上标有参数k的值，请注意某些数出现了 多次。
3 ／＼ 2 1 ／＼ ＼ 1 0 0 ／ 0
图1
例如，knapsack(1)被引用了两次：在计算knapsack(3)和knapsack(2)中分别被引用；而knapsack(0)
更是被引用了三次。如果knapsack(1)和knapsack(0)每次都要被重新计算，则增加的运行时间相当可观
。
下面，我们来看看动态规划是如何解决这个问题的。 (3)按自顶向下记忆化或自底向上的方式求最优解
一般地，如果一个解最优化问题的递归算法经常反复地解重复的子问题，而不是总在产生新的子问题
时，我们说该最优化问题包含重迭子问题。这类问题不宜用分治法求解，因为分治法递归的每一步要求
产生相异的子问题。在这种情况下，采用动态规划是很合适的，因为该方法对每一个子问题只解一次，
然后把解存放在一个表中，以便在解同样的子问题时查阅，充分利用了重迭子问题。一般来说，解决重
迭子问题的方式有两种。
①自顶向下的记忆化方式
该方式的程序流程基本按照原问题的递归定义，不同的是，它专门设置了一张表，以记忆在求解过程
中得出的所有子问题的解。一个记忆的递归算法为每个子问题的解在表中记录一个表项。初始时每个表
项都包含一个特殊值，以示该表项的解有待填入。例如背包问题中： s=-1；(0≤i≤m)
当在递归算法的执行中第一次遇到一个子问题时(即s=-1)，计算其解并填入表中，以后每遇到该子问题
，只要查看表中先前填入的值即可。
下面，我们按照自上而下的记忆化方式，写出求背包问题的递归算法。 函数memorized_knapsack输入背包的负重能力k，返回背包问题的解s[k]。s表应设为全局变量，使得
函数执行后，传出所有子问题的解s(0≤i≤m)。 function memorized_knapsack(k:integer):integer； begin
if s[k]=-1 then begin
s[k]:=0；
for i:=1 to n do if k-w>=0 then begin
t:=memorized_knapsack(k-W)+V； if s[k] < t then s[k]:=t；
end； end；
memorized_knapsack:=s[k]； end；
我们在主程序通过调用memorized_knapsack(m)即可获得背包问题的解。 显然这种自顶向下记忆化的算法效率比重复解重迭子问题的knapsack算法要强一些。此外，在程序中
加入判别哪些子问题需要求解的语句，只解那些肯定要解的子问题，从而节省了时间。
②自底向上的方式
假设我们要解决在分析函数knapsack当中提出的那个具体的背包问题。观察一下在调用
memorized_knapsack(4)的过程中，s[k]被计算出来的顺序。我们发现，首先是s[0]被计算出来，然后是
s[1]，s[2]，最后s[3]被计算出来，这与调用的次序正好相反。
动态规划的执行方式是自底向上，所有的子问题计算一次，充分利用重迭子问题。因此，我们很自然
就想到与这种自底向上的执行方式相应的采用自底向上的方式递推所有子问题的最优值。
我们知道，计算负重能力为k的背包问题的解仅依赖于计算负重能力小于k的背包问题的解，因此填s
表的方式与解决负重能力递增的背包问题相对应：
最初设定负重能力为0的背包问题的解s[0]=0。然后依次考虑负重能力为1，2，…，m的背包问题的解
。每填入一个s[k](0≤k≤m)时，充分利用所有重迭子问题的解：s[k-w](0≤i≤n，k-w≥0)
下面是按照自底向上方式计算背包问题的算法流程。过程knapsack_order输入背包的负重能力k，s表
设为全局变量。过程执行后所有子问题的解通过s表传给主程序。 procedure knapsack_order(k:integer); begin
for i:=1 to k do s:=0; for j:=1 to k do for i:=1 to n do if j-w>=0 then begin
t:=s[j-w]+v;
if s[j] < t then s[j]:=t; end; end;
我们在主程序调用knapsack_order(m)，过程执行后s[m]即为背包问题的解。
最后，我们分析一下背包问题的动态规划解法的复杂度。所需的存储开销主要在s表上，其空间复杂
度是O(m)。而整个s表用两重循环求出，循环内语句的执行只需常数时间，因此，时间复杂度是O(m,n)。
自顶向下的记忆化是动态规划的一种变形。动态规划的执行方式是自底向上，因此自底向上的计算方
式是与动态规划的执行方式相一致的。它无需递归代价，且维护记忆表的开销也要小些，因此其效率通
常好于自顶向下的记忆法。
但是，在动态规划的执行过程中，并不是所有的子问题都要用到它。对某个具体问题而言，可能有大
部分子问题的最优值是不必计算的。自底向上的计算方式无法判断那些子问题是需要求解的，所以它将
一视同仁地处理所有的子问题，这就可能会把大量的时间都花在计算不必解决的子问题上；而自顶向下
的记忆法可以判断那些子问题是需要求解的，只解那些肯定要解的子问题，在这个意义上，自顶向下的
算法效率又好于自底向上。所以到底那种方式效率更高，我们要具体问题具体分析。
最后，给出求解背包问题的程序如下： {//背包问题程序} program knapsack;
const
maxn=100; maxm=1000; var
m,n:integer;
S:array[0..maxm] of integer; v,w:array[1..maxn] of integer; {//输入数据}
procedure read_data; var i:integer;
begin
read(m,n);
for i:=1 to n do read(v,w); end;
{//采用自底向上的方式求解背包问题} procedure knapsack_order; var i,j,t:integer; begin
for i:=1 to m do s:=0; for j:=1 to m do
for i:=1 to n do if j-w>=0 then begin
t:=s[j-w]+v;
if s[j] < t then s[j]:=t; end; end;
{//主程序}
begin
read_data;
knapsack_order; writeln(s[m]); end.
二．动态规划的正向思维法
正向思维法是指从初始状态或边界状态出发，利用某种规则不断到达新的状态，直到问题目标状态的方
法。动态规划的正向思维法，正是从已知最优值的初始状态或边界状态开始，按照一定的次序遍历整个
状态空间，递推出每个状态所对应问题的最优值。
提出动态规划的正向思维法的根本原因，是为了摆脱逆向思维法当中那种将大问题转化为子问题的思
维框框，提供一种新的思维方式。在正向思维法中，我们不再区分原问题和子问题，将动态规划的过程
看成是从状态到状态的转移。我们将所有的状态构造出一个状态空间，并在状态空间中设想一个状态网
络，若对两个状态i,j，存在决策变量di使t(i，di)=j，则向状态网络添加有向边。给定己知最优值的初
始状态或边界状态，我们可以沿着有向边推广到未知最优值的新状态，利用状态转移方程得到新状态的
状态变量的最优值。我们可以用这种方式遍历整个状态空间，得到每个状态的状态变量的最优值。
因为正向思维法中不再区分原问题、子问题、子子问题，所以我们不再按照问题被递归调用求解的相
反次序的方法确定状态最优值的计算次序。从上面我们知道可以按照状态的拓扑序列来计算每个状态的
最优值，于是我们用一个新的名词\"阶段\"来描述在状态空间遍历的过程中，各个状态最优值的计算次序
。我们将每个状态和一个阶段挂钩，前一个阶段的状态先计算，后一个阶段的状态后计算。有的时候我
们甚至将一组状态和一个阶段挂钩，前一个阶段的那组状态先计算，后一个阶段的那组状态后计算，而
在同一个阶段内，那些状态的计算次序可以是任意的。
动态规划的正向思维法的要点可归纳为以下三个步骤： (1)构造状态网络；
(2)根据状态转移关系和状态转移方程建立最优值的递推计算式： (3)按阶段的先后次序计算每个状态的最优值。
在下一节\"最短路问题\"当中，我们将结合最短路问题来示范动态规划的正向思维法。
动态规划的正向思维法带给我们什么启示呢?动态规划需要按阶段遍历整个状态空间，因此动态规划
的效率取决于状态空间的大小和计算每个状态最优值的开销：如果状态空间的大小是多项式的，那么应
用动态规划的算法就是多项式时间的；如果状态空间的大小是指数的，那么应用动态规划的算法也是指
数时间的。因此，找一个好的状态划分对动态规划的效率是至关重要的。 将这个结论应用到逆向思维上，我们得出如下结果：一个问题的最优子结构常常暗示了动态规划的状
态空间。典型的情况是，某一个特定问题可有几类\"自然\"的子问题，不同的子问题往往意味着不同的最
优子结构，从而我们得到不同的状态划分方案。但是由这些不同的状态得到的算法的效率可能差异极大
。例如，某个问题的输入是一个有序序列，有两类\"自然\"的子问题，一类子问题的输入是原问题输入序
列的所有子序列，另一类子问题的输入是原问题输入序列的任意元素构成的新序列。显然若我们采用后
者的最优子结构来建立状态，它的状态空间必然远远大于基于前者的状态空间。那末基于后者的状态空
间的动态规划则要解许多不必要的问题，使得算法的效率骤然下降。 从动态规划的正向思维法的分析可以看出，我们从已知最优值的初始状态和边界状态出发，利用最优
化原理，一步一步向未知的目标状态推进，直到目标状态的最优值解决。这种\"从己知推广到未知\"的思
维，正是动态规划正向思维法的精髓。大家在运用动态规划的正向思维法时如果能掌握这一点，那么就 能达到应用自如的境界。
在应用动态规划求解的问题的过程中，希望读者能够注意从题目的分析中领会：应用动态规划解题是
富于技巧和创造性的，没有固定的模式可套；题目出现的形式多种多样，而且大部分表面上与动态规划
看不出直接的联系。只有在充分把握其思想精髓的前提下大胆联想，才能达到得心应手，灵活运用的境 界。
三．动态规划设计方法的一般模式
动态规划所处理的问题是一个多阶段决策问题，一般由初始状态开始，通过对中间阶段决策的选择，达
到结束状态。这些决策形成了一个决策序列，同时确定了完成整个过程的一条活动路线(通常是求最优的
活动路线)。如图所示。动态规划的设计都有着一定的模式，一般要经历以下几个步骤。
┌───┐ ┌───┐ ┌───┐
初始状态→│决策１│→│决策２│→…→│决策ｎ│→结束状态 └───┘ └───┘ └───┘ 图1 动态规划决策过程示意图
(1)划分阶段：，按照问题的时间或空间特征，把问题分为若干个阶段。在划分阶段时，注意划分后
的阶段一定要是有序的或者是可排序的，否则问题就无法求解。
(2)确定状态和状态变量：将问题发展到各个阶段时所处于的各种客观情况用不同的状态表示出来。
当然，状态的选择要满足无后效性。
(3)确定决策并写出状态转移方程：因为决策和状态转移有着天然的联系，状态转移就是根据上一阶
段的状态和决策来导出本阶段的状态。所以如果确定了决策，状态转移方程也就可写出。但事实上常常
是反过来做，根据相邻两段各状态之间的关系来确定决策。
(4)寻找边界条件：给出的状态转移方程是一个递推式，需要一个递推的终止条件或边界条件。
(5)程序设计实现：动态规划的主要难点在于理论上的设计，一旦设计完成，实现部分就会非常简单
。
根据上述动态规划设计的步骤，可得到大体解题框架如图2所示。 图2 动态规划设计的一般模式
上述提供了动态规划方法的一般模式，对于简单的动态规划问题，可以按部就班地进行动态规划的设
计。
下面，给出一个利用动态规划方法求解的典型例子。
【例题6】数字三角形问题。图3示出了一个数字三角形宝塔。数字三角形中的数字为不超过100的整
数。现规定从最顶层走到最底层，每一步可沿左斜线向下或右斜线向下走。 任务一：假设三角形行数≤10，键盘输入一个确定的整数值M，编程确定是否存在一条路径，使得沿着
该路径所经过的数字的总和恰为M，若存在则给出所有路径，若不存在，则输出\"NO Answer!\"字样。
任务二：假设三角形行数≤100，编程求解从最顶层走到最底层的一条路径，使得沿着该路径所经过
的数字的总和最大，输出最大值。
输人数据：由文件输入数据，任务一中文件第一行是三角形的行数N和整数值 M。以后的N行分别是从
最顶层到最底层的每一层中的数字。任务二中文件数据格式同任务一，只是第一行中没有整数值M。在例
子中任务二的文件数据表示如下：
输入：5 7 输出：
3 8 7 输出路径和最大值 8 1 0 3 8 或\"No Answer!\"字样。 2 7 7 4 8 1 0 4 5 2 6 5 2 7 4 4 图3 数字三角形 4 5 2 6 5
【分析】对于这一问题，很容易想到用枚举的方法去解决，即列举出所有路径并记录每一条路径所经过
的数字总和。然后判断数字总和是否等于给定的整数值M或寻找出最大的数字总和，这一想法很直观，而
且对于任务一，由于数字三角形的行数不大(<＝10)，因此其枚举量不是很大，应该能够实现。但对于任
务二，如果用枚举的方法，当三角形的行数等于100时，其枚举量之大是可想而知的，显然，枚举法对于
任务二的求解并不适用。其实，只要对对任务二稍加分析，就可以得出一个结论：
如果得到一条由顶至底的某处的一条最佳路径，那么对于该路径上的每一个中间点来说，由顶至该中
间点的路径所经过的数字和也为最大。因此该问题是一个典型的多阶段决策最优化的问题。算法设计与
分析如下：
对于任务一，合理地确认枚举的方法，可以优化问题的解法。由于从塔顶到底层每次都只有两种走法
，即左或右。设\"0\"表示左， \"1\"表示右，对于层数为N的数字塔，从顶到底的一种走法可用一个N-1位
的二进制数表示。如例中二进制数字串1011，其对应的路径应该是：8-1-4-6。这样就可以用一个N-l位
的二进制数来模拟走法和确定解的范围。穷举出从0到2n-1个十进制数所对应的N-1位二进制串对应的路
径中的数字总和，判定其是否等于M而求得问题的解。
对于任务二，采用动态规划中的顺推解法。按三角形的行划分阶段，若行数为 n，则可把问题看做一
个n-1个阶段的决策问题。从始点出发，依顺向求出第一阶段、第二阶段……第n-1阶段中各决策点至始
点的最佳路径，最终求出始点到终点的最佳路径。
设：fk(Uk)为从第k阶段中的点Uk至三角形顶点有一条最佳路径，该路径所经过的数字的总和最大，
fk(Uk)表示为这个数字和；
由于每一次决策有两个选择，或沿左斜线向下，或沿右斜线向下，因此设：
Uk1为k-1阶段中某点Uk沿左斜线向下的点； Uk2为k-1阶段中某点Uk沿右斜线向下的点；
dk(Uk1)为k阶段中Uk1的数字；dk(Uk2)为k阶段中Uk2的数字。 因而可写出顺推关系式(状态转移方程)为：
fk(Uk)=max{fk-1(Uk)+dk(Uk1)，fk-1(Uk)+dk(Uk2)}(k=1，2，3，…，n) f0(U0)＝0
经过一次顺推，便可分别求出由顶至底N个数的N条路径，在这N条路径所经过的N个数字和中，最大值 即为正确答案。
四．动态规划方法实现的灵活性与技巧性
上述例子给出了一般情况下的动态规划思维过程。一些较为简单的问题可以\"按部就班\"来操作，但大多
数的\"动态规划\"问题，特别是作为信息学竞赛中的\"动态规划\"问题，考察的知识是多方面的，应用的技
巧是灵活多变的。下面给出上述例5变形的例子。
【例题7】花店橱窗布置问题('99IOI试题)。假设以最美观的方式布置花店的橱窗，有F束花，每束花
的品种都不一样，同时，至少有同样数量的花瓶，被按顺序摆成一行，花瓶的位置是固定的，并从左到
右，从1到V顺序编号，V是花瓶的数目，编号为1的花瓶在最左边，编号为V的花瓶在最右边，花束可以移
动，并且每束花用1到F的整数惟一标识，标识花束的整数决定了花束在花瓶中列的顺序即如果I < J，则
花束I必须放在花束J左边的花瓶中。例如，假设杜鹃花的标识数为1，秋海棠的标识数为2，康乃馨的标
识数为3，所有的花束在放人花瓶时必须保持其标识数的顺序，即：杜鹃花必须放在秋海棠左边的花瓶中
，秋海棠必须放在康乃馨左边的花瓶中。如果花瓶的数目大于花束的数目，则多余的花瓶必须空，即每
个花瓶中只能放一束花。
每一个花瓶的形状和颜色也不相同，因此，当各个花瓶中放人不同的花束时会产生不同的美学效果，
并以美学值(一个整数)来表示，空置花瓶的美学值为0。在上述例子中，花瓶与花束的不同搭配所具有的
美学值，可以用如下表格表示：
┌───┬───┬───┬───┬───┬───┐
│ │花瓶1 │花瓶2 │花瓶3 │花瓶4 │花瓶5 │ ├───┼───┼───┼───┼───┼───┤ │杜鹃花│ 7 │ 23 │ -5 │ -24 │ 16 │
├───┼───┼───┼───┼───┼───┤ │秋海棠│ 5 │ 21 │ -4 │ 10 │ 23 │
├───┼───┼───┼───┼───┼───┤ │康乃馨│ -21 │ 5 │ -4 │ -20 │ 20 │ └───┴───┴───┴───┴───┴───┘
根据表格，杜鹃花放在花瓶2中，会显得非常好看，但若放在花瓶4中则显得很难看。
为取得最佳美学效果，必须在保持花束顺序的前提下，使花的摆放取得最大的美学值，如果具有最大
美学值的摆放方式不止一种，则输出任何一种方案即可。题中数据满足下面条件：1≤F≤100，F≤V≤
100，－50≤AIJ≤50，其中AII是花束I摆放在花瓶J中的美学值。输入整数F，V和矩阵(AIJ)，输出最大
美学值和每束花摆放在各个花瓶中的花瓶编号。
[分析]问题实际就是给定F束花和V个花瓶，以及各束花放到不同花瓶中的美学值，要求你找出一种摆
放的方案，使得在满足编号小的花放进编号小的花瓶中的条件下，美学值达到最大。
(1)将问题进行转化，找出问题的原型。首先，看一下上述题目的样例数据表格。
将摆放方案的要求用表格表现出来，则摆放方案需要满足：每行选且只选一个数(花瓶)；摆放方案的
相邻两行中，下面一行的花瓶编号要大于上面一行的花瓶编号两个条件。这时可将问题转化为：给定一
个数字表格，要求编程计算从顶行至底行的一条路径，使得这条路径所经过的数字总和最大(要求每行选
且仅选一个数字)。同时，路径中相邻两行的数字，必须保证下一行数字的列数大于上一行数字的惺 ?
br> 看到经过转化后的问题，发现问题与例题6的数学三角形问题十分相似，数字三角形问题的题意
是：
给定一个数字三角形，要求编程计算从顶至底的一条路径，使得路径所经过的数字总和最大(要求每
行选且仅选一个数字)。同时，路径中相邻两行的数字，必须保证下一行数字的列数与上一行数字的列数
相等或者等于上一行数字的列数加1。
上例中已经知道：数字三角形中的经过数字之和最大的最佳路径，路径的每个中间点到最底层的路径
必然也是最优的，可以用动态规划方法求解，对于\"花店橱窗布置\"问题经过转化后，也可采取同样的方
法得出本题同样符合最优性原理。因此，可以对此题采用动态规划的方法。 (2)对问题原型动态规划方法的修改。\"数字三角形\"问题的动态规划方法为：已知它是用行数来划分
阶段。假设用a[i，j]表示三角形第i行的第j个数字，用p [i，j]表示从最底层到a[i,j]这个数字的最佳
路径(路径经过的数字总和最大)的数字和，易得问题的动态转移方程为： p[n+1,j]=0 (1≤i≤n+1)
p[i,j]=max{p[i+1,j],p[i+1,j+1]}+a[i,j] (1≤i≤i≤n，其中n为总行数)
分析两题的不同之处，就在于对路径的要求上。如果用path表示路径中第 i行的数字编号，那么两题
对路径的要求就是：\"数字三角形\"要求path≤path[i+1]≤path+1，而本题则要求path[i+1)>path。
在明确两题的不同之后，就可以对动态规划方程进行修改了。假设用b[i，j]表示美学值表格中第i行
的第j个数字，用q[i，j]表示从表格最底层到b[i，j]这个数字的最佳路径(路径经过的数字总和最大)的
数字和，修改后的动态规划转移方程为： q[i,V+1]=-∞(1≤i≤F+1) q[F，j]=b[F，j](1≤j≤V)
q[i，j]=max{q[i+1，k](j 上面两个状态中求max{q[i+1，k]}的过程进行了大量重复的比较。此时对状态的表示稍作修改，用数 组t[i，j]=max{q[i,k](j≤k≤V+1)}(1≤i≤F， 1≤j≤V)表示新的状态。经过修改后，因为q[i，j]=t [i+1，j+1]+a[i，j]，而t[i，j]=max{t[i，j+1]，q[i,j}(1≤i≤F，1≤j≤V)，所以得出新的状态转移 方程： t[i,V+1]=-∞ (1≤i≤F十1) t[F，j]=max{t[F，j+1]，b[F，j]} (1≤j≤V) t[i,j]=max{t[i，j+1]，t[i+1，j+1]+a[i，j]} (1≤i≤F，1≤j≤V) 这样，得出的最大美学值为t[1,1]，新算法的时间复杂度为O(F*V)，而空间复杂度也为O(F*V)，完全 可以满足1≤F≤V≤100的要求。下面给出这一问题的源程序。 {$A+，B-，D+，E+，F-，G-，I+，L+，N-，O-，P-，Q-，R-，S+，T-，V+，X+} {$M16384，0，655360} program ex；{花店橱窗布置问题} const st1='flower.inp'; {输入文件名} st2='flower.out'; {输出文件名} var f，v：integer； {f为花束的数量；v为花瓶的数量} b：array[1．．100，1．．100] of shortint； {b[i,j]为第i束花放进第j个花瓶的美学值} t：array[1．．101，1．．101] of integer； {t[i，¨为将第i到第f束花放进第j到第v个花瓶所可能得到的最大美学值} procedure readp； {从文件中读入不同花束对应不同花瓶的美学值} var f1：text； i，j：integer； begin assign(f1,st1)；reset(f1)； readln (f1, f, v); for i:=1 to f do for j:=1 to v do read (f1, b [i, j]); close (f1); end; procedure main; {用动态规划对问题求解} var i, j: integer; begin for i:=1 to f+1 do t[i, v+1]:=-9999; for j:=v downto 1 do if t[f, j+l] > b[f, j] then t[f,j]:=t[f, j+1] else t[f,j]:=b[f,j]; {设定动态规划的初始条件，其中-9999表示负无穷} for i:=f-1 downto 1 do for j:= v downto 1 do begin t[i, j]:=t[i, j+1]; if t[i+1, j+1] + b[i, j] > t[i, j] then t[i, j]:=t[i+1, j+1] +b[i, j]; end; end; procedure print; {将最佳美学效果和对应方案输出到文件} var f1: text; i,j,p: integer; {为当前需确定位置的花束编号，p为第i束花应插入的花瓶编号的最小值} begin assign (f1, st2); rewrite (f1); writeln (f1, t [1, 1]); p:=1; for i:=1 to f do begin {用循环依次确定各束花应插入的花瓶} j:=p; while t[i, j] =t[i, p] do inc (j); write (f1, j-1,' '); p:=j; end; writeln (f1); close (f1); end; begin readp; main; print; end. 由此可看出，对于看似复杂的问题，通过转化就可变成简单的经典的动态规划问题。在问题原型的基 础上，通过分析新问题与原问题的不同之处，修改状态转移方程，改变问题状态的描述和表示方式，就 会降低问题规划和实现的难度，提高算法的效率。由此可见，动态规划问题中具体的规划方法将直接决 定解决问题的难易程度和算法的时间与空间效率，而注意在具体的规划过程中的灵活性和技巧性将是动 态规划方法提出的更高要求。 五．应用举例. 【例题1】最短路径问题 现有一张地图，各结点代表城市，两结点间连线代表道路，线上数字表示城市间的距离。如图1所示，试 找出从结点A到结点E的最短距离。 图 1 我们可以用深度优先搜索法来解决此问题，该问题的递归式为 其中是与v相邻的节点的集合，w(v,u)表示从v到u的边的长度。 具体算法如下： function MinDistance(v):integer; begin if v=E then return 0 else begin min:=maxint; for 所有没有访问过的节点i do if v和i相邻 then end; end; begin 标记i访问过了; t:=v到i的距离+MinDistance(i); 标记i未访问过; if t 复杂度为O(n!)，这是一个\"指数级\"的算法，那么，还有没有更好的算法呢？ 首先，我们来观察一下这个算法。在求从B1到E的最短距离的时候，先求出从C2到E的最短距离；而在求 从B2到E的最短距离的时候，又求了一遍从C2到E的最短距离。也就是说，从C2到E的最短距离我们求了两 遍。同样可以发现，在求从C1、C2到E的最短距离的过程中，从D1到E的最短距离也被求了两遍。而在整 个程序中，从D1到E的最短距离被求了四遍。如果在求解的过程中，同时将求得的最短距离\"记录在案\"， 随时调用，就可以避免这种情况。于是，可以改进该算法，将每次求出的从v到E的最短距离记录下来， 在算法中递归地求MinDistance(v)时先检查以前是否已经求过了MinDistance(v)，如果求过了则不用重 新求一遍，只要查找以前的记录就可以了。这样，由于所有的点有n个，因此不同的状态数目有n个，该 算法的数量级为O(n)。 更进一步，可以将这种递归改为递推，这样可以减少递归调用的开销。 请看图1，可以发现，A只和Bi相邻，Bi只和Ci相邻,...，依此类推。这样，我们可以将原问题的解决过 程划分为4个阶段，设 S1={A},S2={B1,B2},S3={C1,C2,C3,C4},S4={D1,D2,D3}，Fk(u)表示从Sk中的点u到 E的最短距离，则 并且有边界条件 显然可以递推地求出F1(A)，也就是从A到E的最短距离。这种算法的复杂度为O(n)，因为所有的状态总数 （节点总数）为n，对每个状态都只要遍历一次，而且程序很简洁。 具体算法如下： procedure DynamicProgramming; begin F5[E]:=0; for i:=4 downto 1 do for each u ∈Sk do begin Fk:=无穷大; for each v∈Sk+1∩δ(u) do if Fk>w(u,v)+Fk+1[v] then Fk:=w(u,v)+Fk+1[v]; end; 输出F1[A]; end 【例题2】生产计划问题 工厂生产某种产品，每单位(千件)的成本为1(千元)，每次开工的固定成本为3(千元)，工厂每季度的最 大生产能力为6(千件)。经调查，市场对该产品的需求量第一、二、三、四季度分别为 2，3，2，4(千件 )。如果工厂在第一、二季度将全年的需求都生产出来，自然可以降低成本(少付固定成本费)，但是对于 第三、四季度才能上市的产品需付存储费，每季每千件的存储费为0.5(千元)。还规定年初和年末这种产 品均无库存。试制订一个生产计划，即安排每个季度的产量，使一年的总费用(生产成本和存储费)最少 。 这是一个明显的多阶段问题，我们按照计划时间自然划分阶段，状态定义为每阶段开始时的存储量xk， 决策为每个阶段的产量uk，记每个阶段的需求量（已知）为dk，则状态转移方程为： 设每个阶段开工固定成本费用为a，生产单位数量产品的成本为b，每阶段单位数量产品的存储费用为ｃ ，阶段指标为阶段的生产成本费用和存储费用之和，即： 指标函数Vkn为vk之和，最优值函数fk(xk)为从第k阶段的状态xk出发到过程终结的最小费用，满足 其中允许决策集合Uk由每阶段的最大生产能力决定，设过程终结时允许存储量为x0n+1，则终端条件为： 【例题3】Bitonic旅行路线问题 欧几里德货郎担问题是对平面给定的n个点确定一条连结各点的、闭合的游历路线问题。图1(a)给出了七 个点问题的解。Bitonic旅行路线问题是欧几里德货郎担问题的简化，这种旅行路线先从最左边开始，严 格地由左至右到最右边的点，然后再严格地由右至左到出发点，求路程最短的路径长度。图1（b）给出 了七个点问题的解。 图1 请设计一种多项式时间的算法，解决Bitonic旅行路线问题。 首先将n个点按X坐标递增的顺序排列成一个序列L=<点1，点2，…，点n>。显然L[n]为最右点，L[1]为最 左点。由于点1往返经过二次(出发一次，返回一次)，因此点1拆成两个点：L[0]=L[1]=点1。 设： \" Wi,j -- 边 \" Wi..j -- j-i条连续边 成的路径称为连续路径； \" d --从点i出发由左至右直到n点后再由右至左到达点i-1的最短距离。d的递归式如下: 我们专门设置了一张记忆表k(1≤i≤n)，记下使得d最小的J值。显然递归式的边界d[n]=Wn,n-1 ，k[n] =n 。 由d的递归式和记忆表k的定义可以看出，在由点i-1至点i的最短路上，点i至k的子路径上的点序号是遂 一递增的，为由左至右方向上的连续子路径。按照递归定义，若k≠N且 k[k+1]≠N，则点k[k+1]+1至点 k[k[k+1]+1]也是由左至右方向上的连续子路径；否则k[k+1]至k+1为由右至左方向上的连续子路径，该 子路径上的点序号是遂一递减的。 显然要使d最小，必须分别使d[i+1]…d[n-1],d[n]最小,d包含了d[i+1]…d[n]最小的子问题，因此该问 题具有最优子结构和重叠子问题性质，满足动态规划法适用的条件。为了提高算法效率，我们从d[n]出 发，运用动态规划方法依次求d[n-1],d[n-2],…,d[1]，充分利用重叠子问题。最后求得的d[1]便是最短 游历路线的距离；从点1出发，顺着记忆表k的指示可以递归递输出这条游历路线。 【例题4】皇宫看守 SGOI2001第二次竞赛试题第4题，中国教育曙光网举办 问题描述 太平王世子事件后，陆小凤成了皇上特聘的御前一品侍卫。 皇宫以午门为起点，直到后宫嫔妃们的寝宫，呈一棵树的形状；某些宫殿间可以互相望见。大内保卫森 严，三步一岗，五步一哨，每个宫殿都要有人全天候看守，在不同的宫殿安排看守所需的费用不同。 可是陆小凤手上的经费不足，无论如何也没法在每个宫殿都安置留守侍卫。 编程任务： 帮助陆小凤布置侍卫，在看守全部宫殿的前提下，使得花费的经费最少。 数据输入： 输入数据由文件名为INPUT.TXT的文本文件提供。输入文件中数据表示一棵树，描述如下： 第1行 n，表示树中结点的数目。 第2行至第n+1行，每行描述每个宫殿结点信息，依次为：该宫殿结点标号i（0 对于一个n（0 < n <= 1500）个结点的树，结点标号在1到n之间，且标号不重复。 数据输出： 输出到OUTPUT.TXT文件中。输出文件仅包含一个数，为所求的最少的经费。 如左图的输入数据示例 输出数据示例 在下面我们用根结点的标号来表示一棵树，树T就是根结点标号为T的树。 \" 设f(T,0)表示对于一棵树T，不在T的树根上布置守卫的情况下，监控T的全部节点所需的最少的费用； \" 设f(T,1)表示对于一棵树T，不在T的树根上布置守卫的情况下，监控除了T的根结点以外的其他全部节 点所需的最少的费用，当然也可以监控住T的根结点，不过不是强行要求的； \" 设f(T,2)表示对于一棵树T，在T的树根上布置守卫的情况下，监控T的全部节点所需的最少的费用； 假设T的儿子节点为T1,T2,…,Tn；则我们可以得到递归公式： （1） （2） （3） 下面说明上面的三个公式的含义。 如果T的根不布置守卫，并且要求监控T的所有结点，则必须保证T的子结点中有一个结点Tk的根上布置了 一个守卫，这样在Tk的根上的守卫可以同时看守T的根。至于T的其他子结点(i=1,2,..n,i≠k)，可以在 树根上布置守卫，也可以不布置，但是必须监控住自己所有的结点（因为T的根上没有守卫），因此选择 最优的方案min{f(Ti,0),f(Ti,2)}。这样就得到了（1）式； 如果T的根不布置守卫，并且要求监控除了T的根结点以外的其他全部节点，则必须保证T的所有的子结点 Ti都被监控，而不用管Ti的根上是否有守卫。于是每个子节点Ti取最优的方案min{f(Ti,0),f(Ti,2)}。 这样就得到了（2）式；请注意，有可能f(T,0)=f(T,1)，因为f(T,1)只是要求监控除了T的根结点以外的 其他全部节点，也就是可以选择不监控T的根，而不是不允许监控T的根。当存在一个1<=k<=n，f(Tk,0) >=f(Tk,2)的时候，（2）和（1）等价，这时候f(T,1)=f(T,0)； 如果规定T的根布置了守卫，则T的所有的子结点上可以布置也可以不布置守卫，而且T的所有的子结点Ti 的根原来可以被监控也可以不被监控，这是因为如果原来Ti的根没有被监控，则可以被T的根上布置的那 个守卫监控。因此Ti选择最优的方案min{f(Ti,0),f(Ti,1),f(Ti,2)}。这样就得到了（3）式, 这里ω (T)表示在根结点T上布置守卫的代价。实际上，在（3）中的min只要对f(Ti,1)和f(Ti,2)取min就可以了 ，因为根据（2）可以知道f(Ti,1)<=f(Ti,0)。 如果T是整棵树的树根的话，只要求出f(T,0),f(T,2)取较小者就是结果。 对于T没有儿子的情况（结点T为叶子），我们给出上面递归公式的边界条件： （4） （5） （6） 注意，这里我们做了一点特殊规定，因为根据前面对f(T,0) f(T,1) f(T,2)的定义可以知道，在T是叶子 的情况下不在T的树根上布置守卫的情况下而要监控T的全部节点使不可能的，f(T,0)实际上是不存在的 ，但是为了使上面的公式（1）-（3）能够适用于边界条件，我们规定了（4）式对于T是叶子的情况成立 。这并不影响公式（1）-（3）的正确性。（5）说明在T是叶子的情况下，不在T的树根上布置守卫的情 况下并监控除了T的根结点以外的其他全部节点，最节约的办法是不布置任何的守卫，这样代价最少为0 ；（6）说明在T是叶子的情况下，在T的树根上布置守卫的情况下并监控T的全部节点的办法就是在节点T 上布置一个守卫，代价为。 下面说说如何编程实现对于这个算法。对于这个问题，虽然可以自底向上的计算，但是不如自顶向下的 计算方便。我们采用备忘录法，用一个n*3的数组记录所有的f函数。因为n<=1500；n*3不过才4500,显然 不会有内存不足的问题。之所以采用自顶向下的备忘录方法，是因为输入的数据是一棵树，从树的根找 到树的子结点肯定比从子节点找到父结点方便。不过也可以自底向上，这时可以用一个数组parent存储 所有的节点的父结点（也就是树的父结点树组描述法），parent就是结点i的父结点。这样每次要扫描一 遍整个数组，太麻烦了一点。所以我们干脆选择最自然的自顶向下的计算方式。 源程序guard.c在Turbo C 2.0下面调试通过，并且通过了所有的测试数据 因篇幅问题不能全部显示，请点此查看更多更全内容