动态规划及其应用内容提要引例：数字三角形在上面的数字三角形中寻找一条从顶部到底边的路径，使得路径上所经过的数字之和最大。路径上的每一步都只能往左下或右下走。只需要求出这个最大和即可，不必给出具体路径。三角形的行数大于1小于等于100数字为0-99输入格式：//三角形行数。下面是三角形738810274445265要求输出最大和算法一：深搜（递归实现）vara:array[1..5,1..5]ofinteger;i,j:integer;n:integer;Functionlp(I,j:integer):integer;varx,y:integer;beginif(i=n)thenlp:=a[i][j]elsebeginx:=lp(i+1,j);y:=lp(i+1,j+1);if(x<y)thenx:=y;lp:=x+a[i][j];end;End;为什么超时？数字三角形为什么超时？如果每算出一个MaxSum(r,j)就保存起来，则可以用o(n2)时间完成计算。因为三角形的数字总数是n(n+1)/2此时需要的存储空间是：a[1..100,1..100];//用于存储三角形中的数字b[1..100,1..100];//用于存储每个MaxSum(r,j)vara,b:array[1..5,1..5]ofinteger;i,j,n:integer;Functionlp(I,j:integer):integer;varx,y:integer;beginif(i=n)thenbeginlp:=a[i][j];b[i,j]:=a[i,j];endelseifb[i,j]=0thenbeginx:=lp(i+1,j);y:=lp(i+1,j+1);if(x<y)thenx:=y;beginlp:=x+a[i][j];b[i,j]:=x+a[i,j];end;endelselp:=b[i,j];End;什么是动态规划？阶段状态决策算法模式图程序框架例1：拦截导弹（Noip2002）拦截导弹（Noip2002）拦截导弹（Noip2002）例2：最小代价子母树[问题描述]设有n堆沙子排成一排，其编号为1，2，3，…，n（n≤100）。每堆沙子有一定的数量，如下表13781621418现在要将n堆沙子归并成一堆。归并的过程为每次只能将相邻的两堆沙子堆成一堆，这样经过n-1次归并之后最后成为一堆，如上面7堆沙子，可以有多种方法归并成一堆，其中的2种方法如下图：归并的代价是这样定义的，将两堆沙子归并为一堆时，两堆沙子数量的和称为归并2堆沙子的代价。如上图中，将13和7归并为一堆的代价为20。归并总代价指的是将沙子全部归并为一堆沙子的代价的和，如上面的2种归并方法中，（a）的总代价为20＋24＋25＋44＋69＋87＝267（b）的总代价为15＋37＋22＋28＋59＋87＝248由此可见，不同归并过程得到的总的归并代价是不一样的。问题：当n堆沙子的数量给出之后，找出一种合理的归并方法，使总的归并代价为最小。[问题分析]为了说明算法的过程，我们先分析一些简单的情况。（1）n=2当n=2时，仅有一种堆法，因此总的归并代价为2堆沙子数量的和。（2）n=3当n=3时，有2种堆法。从上图可以看到它们总的归并代价分别为44和35。下面我们分析产生这种现象的原因。（3）n=4当n=4时，共有5种归并的方法，它们的总代价分别为94，95，80，88，87，最小的归并总代价为（c）80。上面的5种方法可以分为三类。第一类包括（a），（b），基本方法是归并前面的三堆，再归并最后的一堆，由于最后一堆归并的代价是相同的，所以在归并前面三堆时不同的方法将产生不同的结果。（a）中归并三堆的代价为54，（b）中归并三堆的代价为55，所以第一类方法中的（a）比（b）优。第二类仅有一种方法（c），分别归并2堆的代价为20，20，相加为40。第三类包括（d），（e），基本方法是归并后面的三堆，再归并第一堆，由于最后一次归并代价是相同的，所以归并后三堆的方法不同将产生不同的结果，由上面的分析可知，方法（e）比方法（d）优。引入记号f（i，j）表示从i堆沙子到j堆沙子的归并最小代价数。从上面讨论可知f(1,4)＝min{f(1,3)，f(1,2)+f(3,4)，f(2,4)}＋40而f（1，3）＝min{f（1，2），f（2，3）}＋34f（1，2）＝20f（3，4）＝20f（2，3）＝21f（2，4）＝min{f（2，3）