文档介绍：实验二动态规划（3学时）
1、 实验目的
1） 理解动态规划算法的概念；
2） 掌握动态规划算法的基本要素；
3） 掌握设计动态规划算法的步骤；
4） 针对具体问题，能应用动态规划法设计有效算法；
5） 用C++实现算法，并且分实验二动态规划（3学时）
1、 实验目的
1） 理解动态规划算法的概念；
2） 掌握动态规划算法的基本要素；
3） 掌握设计动态规划算法的步骤；
4） 针对具体问题，能应用动态规划法设计有效算法；
5） 用C++实现算法，并且分析算法的效率。
2、 实验设备及材料
硬件设备：PC
操作系统：Windows XP
开发工具：VC++
3、 实验内容：
问题描述
给定一个由n行数字组成的数字三角形，试设计一个算法，计算出从三角形的顶到底的一 条路径，使该路径经过的数字总和最大。
编程任务
试设计一个算法，计算出从三角形的顶到底的一条路径，使该路径经过的数字总和最大。
样例
例如：如下所示图
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
得到最优解30
4、实验方法步骤及注意事项
①
1、
2、
3、
②
实验步骤
根据题意找出最优解的性质，并刻画其结构特征。
以自底向上的方式计算出最优值。
根据计算最优值时得到的信息，构造最优解。
解题思路
从倒数第二行p[n-2][0]开始，将自己与下一行同列的数相加再和自己与下一行下一列的数相 加的结果比较，将大的存放在自己中。
③代码为
#include <iostream>
#include <fstream>
using namespace std;
void Find(int** p,int n)
{
int sum=0;
int i,j;
for(i=n-2;i>=0;i--)
{
for(j=0;j<i+1;j++)
{
if((p[i+1][j]+p[i][j])<(p[i][j]+p[i+1][j+1]))
p[i][j]=p[i][j]+p[i+1][j+1];
else
p[i][j]=p[i+1][j]+p[i][j];
}
}
printf("%d \n",p[0][0]);
}
/////////////////////////////////////////////////////////////////
void main()
{
int n;
FILE *fp;
int i,j;
if((fp=fopen("","r"))==NULL)
{
cout<<"不能打开文件 !\n\
解决办法是：\n\
建立文件 o \n\
。\n"; exit(0);
}
fscanf(fp,”%d”,&n);
cout<<n<<endl;
int **p=new int*[n];
for(i=0;i<n;i++)
}
for(i=0;i<n;i++)
{
for(j=i;j>=0;j--)
fscanf(fp,”%d”,&p[i][j]);
}
for(i=0;i<n;i++)
{
for(