寒假训练——热身—递推——数塔
题目
代码
#include <iostream>
#include <stdio.h>
#include <math.h>
using namespace std;
int main()
{
int n,m,i,j;
int a[105][105];
cin >>m;
while(m--)
{
cin >>n;
for(i=0;i<n;i++)
for(j=0;j<=i;j++)
{
cin >> a[i][j];//先输入每个数以及(i,j)位置
}
for(i=n-1;i>=1;i--)//i=0时上面没数1所以取到1
for(j=0;j<i;j++)
{
if(a[i][j]>a[i][j+1])//判断与倒数第二行链接的倒数第一行的两个数的大小,选择大的相加
a[i-1][j]+=a[i][j];
else
a[i-1][j]+=a[i][j+1];
}
cout << a[0][0]<<endl;//此时最顶端的数为最大路径上的所有数相加
}
return 0;
}