描述
如图所示，是一个数字搭成的三角形。
若起始位置在三角形的顶端，结束位置在三角形底边，每一步只能向下方或向右下角移动一格。请编程计算一条路径，使得路径上经过的数字和最大。（图中路径7→3→8→7→5经过的数字和最大，为7+3+8+7+5=30）
输入
第一行包含一个正整数T (1≤T≤10)，表示有T组测试用例。 每组用例有多行，第一行包含一个正整数N（2≤N≤100），接下来有n行，第i行包含i个自然数（不超过100），以空格分隔，表示数字三角形第i层。
输出
每组用例输出一行，仅包含一个整数，即所求路径上的数字和。
样例输入
1
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
样例输出
30
#include<iostream>
using namespace std; inline int max(int a,int b)
{
return a>b?a:b;
}
const int MAX=101; int main()
{
int t,n,i,j;
int a[MAX][MAX];
int p[MAX][MAX];
cin>>t;
while(t--)
{
cin>>n;
for(i=0;i<n;i++)
for(j=0;j<=i;j++)
cin>>a[i][j];
for(i=0;i<n;i++)
p[n-1][i]=a[n-1][i];
for(i=n-2;i>=0;i--)
{
for(j=0;j<=i;j++)
{
p[i][j]=a[i][j]+max(p[i+1][j],p[i+1][j+1]);
}
}
cout<<p[0][0]<<endl;
}
return 0;
}