2.5 动态规划法
2.5.1 动态规划法的设计思想
动态规划法（dynamicprogramming）也是将待求解问题分解成若干个子问题，但是子问题之间往往不是相互独立的，如果用分治法求解，这些子问题的重叠部分被重复计算多次。动态规划法将每个子问题求解一次并将其解保存在一个表格（通常采用数组）中，当需要再次解此子问题时，只是简单地通过查表获得该子问题的解，从而避免了大量重复计算。动态规划法的一般过程如图2-6所示。
图2-6 动态规划法的求解过程
例如，Fibonacci数列存在如下递推关系式：
注意到计算F（n）是以计算它的两个重叠子问题F（n-1）和F（n-2）的形式来表达的，可以利用一维数组fib[n+1]填入F（n）的值（补充定义F（0）=0），开始时，根据递推式的初始条件可以直接填入0和1，然后根据递推式填写其他元素，如图2-7所示。显然，数组中最后一项就是F（n）的值。
图2-7 动态规划法求解Fibonacci数列的填表过程
一般来说，动态规划法的求解过程由以下三个阶段组成。
（1）划分子问题：将原问题分解为若干个子问题，并且子问题之间具有重叠关系；
（2）动态规划函数：根据子问题之间的重叠关系找到子问题满足的递推关系式（称为动态规划函数）；
（3）填写表格：设计表格的形式及内容，根据递推式自底向上计算，实现动态规划过程。
显然，动态规划法的关键是找到体现子问题之间重叠关系的动态规划函数。在本书中，FLOYD算法是利用动态规划法设计的一个高效算法。
2.5.2 算法设计实例——数塔问题
【问题】 如图2-8所示的一个数塔，从数塔的顶层出发，在每一个结点可以选择向左走或向右走，一直走到底层，要求找出一条路径，使得路径上的数值和最大。例如，图2-8所示数塔的最大数值和是：8+15+9+10+18=60。
图2-8 一个5层数塔
【想法】 观察图2-8所示数塔不难发现，从5层数塔的顶层（设顶层为第1层）出发，下一层选择向左走还是向右走取决于两个4层数塔的最大数值和，如图2-10所示，显然，子问题具有重叠的特征。
图2-10 数塔问题的子问题具有重叠关系
如何找到子问题满足的动态规划函数呢？显然，动态规划的求解需要从底层开始进行决策，决策过程如图2-11所示。底层的每个数字可以看做1层数塔，则最大数值和就是其自身，填写图2-11的最下一行；第4层的决策是在最底层决策的基础上进行求解的，可以看做4个2层数塔，如图2-12（a）所示，对每个数塔进行求解，填写图2-11的第4行；第3层的决策是在第4层决策的基础上进行求解的，可以看做3个2层的数塔，如图2-12（b）所示，对每个数塔进行求解，填写图2-11的第3行……最后第1层的决策结果就是数塔问题的整体最优解。
图2-11 数塔问题的决策过程
图2-12 数塔问题的动态规划求解过程
由上述填表过程，可以设计数塔问题的存储结构。将给定的数塔存储为如图2-9所示的下三角矩阵d[n][n]，设二维数组maxAdd[n][n]存储动态规划每一步的决策结果，最后maxAdd[0][0]存储的就是数塔问题的解，则得到如下动态规划函数：
图2-9 数塔的存储
为了求得最大数值和的路径，设数组path[n][n]保存每一次决策所选择的数字在数组d[n][n]中的列下标，例如，path[i][j]的值表示在第i层第j个数塔的决策时所选择的路径，path[i][j]的值定义如下：
【算法】 设函数DataTower完成n层数塔问题并输出对应的路径，算法用伪代码描述如下：
算法：DataTower（d[n][n]）
输入：二维数组d[n][n]
输出：数塔的最大数值和及其路径
1.初始化数组maxAdd的最后一行为数塔的底层数据：
for（j=0；j＜n；j++）
maxAdd[n-1][j]=d[n-1][j]；
2.从第n-1层开始直到第1层对下三角元素maxAdd[i][j]执行下述操作：
2.1 maxAdd[i][j]=d[i][j]+max{maxAdd[i+1][j]，maxAdd[i+1][j+1]}；
2.2 如果选择下标j的元素，则path[i][j]=j，否则path[i][j]=j+1；
3.输出最大数值和maxAdd[0][0]；
4.根据path数组确定每一层决策的列下标，输出路径信息；
【程序】 主函数首先初始化数组d[n][n]为n层数塔的数字，然后调用函数DataTorwer求解最大数值和并输出相应的路径。程序如下：
#include＜stdio.h＞ //使用库函数printf
constintn=5； //假设数塔是5层
intDataTorwer（intd[n][n]）； //函数声明，求解n层数塔
//以下是主函数
intmain（）
{
intd[n][n]={{8}，{12，15}，{3，9，6}，{8，10，5，12}，{16，4，18，10，9}}；
printf（＂最大数值和为：%d\n＂，DataTorwer（d））； //输出最大数值和
return0； //将0返回操作系统，表明程序正常结束
}
//以下是其他函数定义
intDataTorwer（intd[n][n]） //求解数塔问题，数塔存储在数组d[n][n]中
{
intmaxAdd[n][n]={0}，path[n][n]={0}； //初始化
inti，j；
for（j=0；j＜n；j++） //初始化底层决策结果
maxAdd[n-1][j]=d[n-1][j]；
for（i=n-2；i＞=0；i--） //进行第i层的决策
for（j=0；j＜=i；j++） //填写addMax[i][j]，只填写下三角
if（maxAdd[i+1][j]＞maxAdd[i+1][j+1]）
{
maxAdd[i][j]=d[i][j]+maxAdd[i+1][j]；
path[i][j]=j； //本次决策选择下标j的元素
}
else
{
maxAdd[i][j]=d[i][j]+maxAdd[i+1][j+1]；
path[i][j]=j+1； //本次决策选择下标j+1的元素
}
printf（＂路径为：%d＂，d[0][0]）； //输出顶层数字
j=path[0][0]； //顶层决策是选择下一层列下标为path[0][0]的元素
for（i=1；i＜n；i++）
{
printf（＂--＞%d＂，d[i][j]）；
j=path[i][j]； //本层决策是选择下一层列下标为path[i][j]的元素
}
returnmaxAdd[0][0]； //返回最大数值和，即最终的决策结果
}