文档介绍：实验二动态规划算法的应用
一、 实验目的
掌握动态规划算法的基本思想，包括最优子结构性质和基于表格的最优 值计算方法。
熟练掌握分阶段的和递推的最优子结构分析方法。
学会利用动态规划算法解决实际问题。
二、 实验内容
一、 实验目的
掌握动态规划算法的基本思想，包括最优子结构性质和基于表格的最优 值计算方法。
熟练掌握分阶段的和递推的最优子结构分析方法。
学会利用动态规划算法解决实际问题。
二、 实验内容
：数塔问题
给定一个数塔，其存储形式为如下所示的下三角矩阵。在此数塔中，从顶部 出发，在每一节点可以选择向下走还是向右走，一直走到底层。请找出一条路径， 使路径上的数值和最大。
.算法描述：
Steptl:存储信息，将数塔数据存放到二维数组data[][]中。
Stept2:阶段划分，对于数塔问题应该从上而下逐层决策。首先对第四层的每个 数据都进行考虑，选出最优解，然后逐层向上决策，这样逐层递推求出最后结果。 Stept3:最优解和路径的存储，用maxvalue口口存储各个路径的最优值，用 path[][]存储路径oMaxvalue[i][j]初始化为 data[i][j]，Path[i][j]初始化 0， Path[i][j]=0为向左，等于1为向右。
Stept4:信息的输出，路径最优质为maxvalue[1][1]，路径输出为： j=1;for(i=1;i<=n-1;i++)
(
cout<<data[i][j]<<"-->";
j=j+path[i][j];
}
.测试数据
9
12 15
10 6
2
18
9
5
19
7
10
4
16
4实验结果如图:
5关键代码:
#define NUM_MAX 50
void main()
{
int data[NUM_MAX][NUM_MAX];//数据
intmaxvalue[NUM_MAX][NUM_MAX];//最 大值
int path[NUM_MAX][NUM_MAX];;//路径
inti,j,n;
cout<<"please input the number of rows:";
cin>>n;
cout<<"please input the date of several tower:"<<endl;
for(i=1;i<=n;i++)
{
for(j=1;j<=i;j++)
{
ci