计算机算法设计与分析（动态规划 数字三角形问题）

#include <iostream.h> #include <cstdlib> int triangle[100][100]={0}; int Sum(int n) {//用于求路径经过数字的总数最大值 for(int row=n-2;row>=0;row--) //自底向上求解 { for( int col=0;col<=row;col++) { if(triangle[row+1][col]>triangle[row+1][col+1]) //比较上一行的两个叶子节点大小，保存当前节点与较大叶子节点的和 { triangle[row][col]+=triangle[row+1][col]; } else { triangle[row][col]+=triangle[row+1][col+1]; } } } return triangle[0][0]; //最优值在triangle[0][0] } void main(void) { int n; cout<<"input.txt"<<endl; cin>>n; for(int i=0;i<n;i++) { for(int j=0;j<=i;j++) { cin>>triangle[i][j]; //输入每一行的元素 } } cout<<"output.txt"<<endl; cout<<Sum(n)<<endl; //调用Sum()函数得到输出结果 }