数字三角形问题
问题描述：
给定一个有 n 行数字组成的数字三角形，如图所示，试设计一个算法，计算出三角形
顶至底的一条路径，使该路径经过的数字总和最大。
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
编程任务：
对于给定的由 n 行数字组成的数字三角形，编程计算从三角形的顶至底的路径经过的
数字和最大值。
int N;
int fmax(int a,int b)
{
return a> b?a:b;
}
int f(int row,int col)//f(0,0)即为所要求的值,row 表示行数
{
//f(0,0)=max(f(1,0),f(1,1))+a[0][0]
if(row==N-2)//倒数第二层
return fmax(a[row+1][col],a[row+1][col+1])+a[row][col];
return fmax(f(row+1,col),f(row+1,col+1))+a[row][col];
}
int main()
{
/*输入三角形的行数*/
cin>> N;
/*输入每行的数*/
for(int i=0;i <N;i++)
for(int j=0;j <i+1;j++)
cin>> a[i][j];
cout <<f(4,0)<<endl;
cout <<f(3,0)<<endl;
cout <<f(2,0)<<endl;
cout <<f(1,0)<<endl;
cout <<f(0,0)<<endl;
return 0;
}
评论2