在讲述DP算法时，一个经典的例子是数塔问题，它描述如下： 如下所示，数塔需要从顶层到底层。如果每一步只能到相邻的结点，结点的数字之和是多少？ 我已经告诉你了，这是个DP题目，你可以AC吗?
Input
输入数据首先包括一个整数C,每个测试实例的第一行是一个整数N(1 <= N <= 100)，表示数塔的高度，然后用N行数字表示数塔，其中第一行有一个整数，所有整数都在区间[0，99]内。
Output
对于每个测试实例，输出可能得到最大和，每个实例的输出占一行。
Sample
| Inputcopy | Outputcopy |
|---|---|
1 5 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 |
30 |
#include<iostream> #include<stdio.h> #include<cmath> #include<vector> #include<map> #include<cstring> #include<set> #include<stack> #include<queue> #include<algorithm> #include<string> #include<fstream> using namespace std; typedef long long ll; int dx[8]={-2，-1，2，2，1，1，-1，-2； int dy[8]={1，2，2，1，-1，-2，-2，-1； int dx1[4]={-1，0，1，0}； int dy1[4]={0，1，0，-1}； const int mod= 1000000007; int gcd(int a,int b){ return(b?gcd(b,a%b):a); } int lcm(int a,int b){ return(a*b/gcd(a,b)); }
int main(){ int m; cin>>m; while(m--){ int n; int a[150][150]={0}; cin>>n; for(int i=0;i<n;i ) for(int j=0;j<i 1;j ){ scanf("%d",&a[i][j]); } for(int i=n-2;i>=0;i--){ for(int j=0;j<i 1;j ){//从下往上 a[i][j] =max(a[i 1][j],a[i 1][j 1]); } } cout<<a[0][0]<<endl; } }