动态规划设计方法的一般模式

    动态规划所处理的问题是一个多阶段决策问题，一般由初始状态开始，通过对中间阶段决策的选择，达到结束状态。这些决策形成了一个决策序列，同时确定了完成整个过程的一条活动路线(通常是求最优的活动路线)。如图所示。动态规划的设计都有着一定的模式，一般要经历以下几个步骤。

　　　　　┌───┐　┌───┐　　　┌───┐
初始状态→│决策１│→│决策２│→…→│决策ｎ│→结束状态
　　　　　└───┘　└───┘　　　└───┘
     图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到2ⁿ-1个十进制数所对应的N-1位二进制串对应的路径中的数字总和，判定其是否等于M而求得问题的解。
    对于任务二，采用动态规划中的顺推解法。按三角形的行划分阶段，若行数为 n，则可把问题看做一个n-1个阶段的决策问题。从始点出发，依顺向求出第一阶段、第二阶段……第n—1阶段中各决策点至始点的最佳路径，最终求出始点到终点的最佳路径。
    设：f_k(U_k)为从第k阶段中的点Uk至三角形顶点有一条最佳路径，该路径所经过的数字的总和最大，f_k(U_k)表示为这个数字和；
    由于每一次决策有两个选择，或沿左斜线向下，或沿右斜线向下，因此设：
    U_k1为k-1阶段中某点U_k沿左斜线向下的点；
    U_k2为k-1阶段中某点U_k沿右斜线向下的点；
    d_k(U_k1)为k阶段中U_k1的数字；d_k(U_k2)为k阶段中U_k2的数字。
    因而可写出顺推关系式(状态转移方程)为：
    f_k(U_k)=max{f_k-1(U_k)+d_k(U_k1)，f_k-1(U_k)+d_k(U_k2)}(k=1，2，3，…，n)
    f₀(U₀)＝0
    经过一次顺推，便可分别求出由顶至底N个数的N条路径，在这N条路径所经过的N个数字和中，最大值即为正确答案。