动态规划（三）数塔问题问题描述：设有一个三角形的数塔，顶点结点称为根结点，每个结点有一个整数数值。从顶点出发，可以向左走，也可以向右走，
直到底层为止。此时，我们找到一条从根结点开始到达底层的路径。例如13-11-7-14-7就是一条路径。路径上结点中数字之和称为路径
的值，上述路径的值为13+11+7+14+7=52。问题：当三角形数塔给出后，找出一条路径，使路径上的值为最大。输出最大值和形成
路径。数塔问题-分析你怎样分析出数塔问题的最优子结构性质？你怎样分析出数塔问题的重叠子问题性质？数塔问题-分析你怎样递归
地定义最优解的值？提示：为了存储和计算的方便，我们把数塔顺时针旋转45°，成为以下形状，就可以比较容易想出存储结构和写出递归式了
。数塔问题-分析写出完整的数塔问题的递归算法程序（只求最大值，不求路径）？数塔问题-分析你怎样把上述递归式改为递推式？提
示：递推的初始值是什么？问题可分为几个阶段？每个阶段有几个状态？每个状态有几个决策？数塔问题-分析写出完整的动态规划求解数塔问
题的程序。如果要输出最优解的路径，又怎样修改程序？数塔问题-讨论如果把数塔按下三角方式存储，这道题又该怎么做？数塔问题-讨论
本题的阶段数为多少？状态变量与阶段变量的数学关系是什么？决策变量与阶段、状态变量的数学关系是什么？由此，你能不能写出一个动态规
划求解问题的一般程序框架？（这是我们下一次要解决的问题）小夜的程序programshuta;vars:array[1..
100,1..100]ofinteger;q:array[1..100,1..100]ofinteger;n:inte
ger;i,j:integer;beginreadln(n);fillchar(s,sizeof(s),0);fill
char(q,sizeof(q),0);fori:=1tondobeginforj:=1toi
doread(s[i,j]);readln;end;fori:=ndownto1dobegin
forj:=1toidoifq[i+1,j]>q[i+1,j+1]thenq[i,j]:=q
[i+1,j]+s[i,j]elseq[i,j]:=q[i+1,j+1]+s[i,j];end;wri
te(q[1,1]);readln;end.13118127266141581271
324111311812726614158127132411N[I,j]=max(左子树，
右子树）+本身1311812726614158127132411A[n,n]s[I,j]:=
max{s[I,j-1]s[I+1,j]}+a[I,j]S[I,j]:=a[I,j](I=j)13118
1272661415812713241113118127266141581271
32411ForI:=1tondoS[I,I]:=a[I,I];Fork:=n-1To1do
forI:=1tokdobeginj:=n-k+i;1311812726
6141581271324111311812726614158127132411 |
|
