简单DP--数塔

在讲述DP算法时，一个经典的例子是数塔问题，它描述如下：

如下所示，数塔需要从顶层到底层。如果每一步只能到相邻的结点，结点的数字之和是多少？

我已经告诉你了，这是个DP题目，你可以AC吗?

Input

输入数据首先包括一个整数C,每个测试实例的第一行是一个整数N(1 <= N <= 100)，表示数塔的高度，然后用N行数字表示数塔，其中第一行有一个整数，所有整数都在区间[0，99]内。

Output

对于每个测试实例，输出可能得到最大和，每个实例的输出占一行。

Sample

1  5 7  3 8 8 1 0 2 7 4 4 4 5 2 6 5 

30

代码

#include
#include
#include
#include
#include

int main(){
int m;
cin>>m;
while(m--){
int n;
int a[150][150]={0};
cin>>n;
for(int i=0;i for(int j=0;j
scanf("%d",&a[i][j]);
}
for(int i=n-2;i>=0;i--){
for(int j=0;j a[i][j] =max(a[i 1][j],a[i 1][j 1]);
}
}
cout< }
}