1 #include <iostream>
   2 using namespace std;
   3 const int N=110;
   4 int a[N][N];
   5 int f[N][N];
   6 int n;
   7 void Init()
   8 {
   9         scanf("%d",&n);
  10         for(int i=0;i<n;i++)
  11                 for(int j=0;j<=i;j++)
  12                         scanf("%d",&a[i][j]);
  13         memset(f,-1,sizeof(f));
  14 }
  15 int DP(int i,int j)
  16 {
  17         int ans;
  18         if(f[i][j]>=0)
  19                         return f[i][j];
  20         if(i==n-1)
  21                 ans=a[i][j];
  22         else
  23         {
  24                 if(DP(i+1,j)>DP(i+1,j+1))
  25                         ans=a[i][j]+DP(i+1,j);
  26                 else
  27                         ans=a[i][j]+DP(i+1,j+1);                
  28         }
  29         f[i][j]=ans;
  30         return f[i][j];
  31 }
  32 int main()
  33 {
  34         int test;
  35         cin>>test;
  36         while(test-->0)
  37         {
  38                 Init();
  39                 printf("%d\n",DP(0,0));
  40         }
  41 }

   1 //非递规 dp  written by czy
   2 #include <stdio.h>
   3 #include <memory.h>
   4 
   5 int tower[102][102];
   6 int tmax[102][102];
   7 
   8 int max(int &a, int &b){
   9     return a>b?a:b;
  10 }
  11 
  12 int main(){
  13     int Case;
  14     scanf("%d",&Case);
  15         while(Case--){
  16             int tHeight;
  17             scanf("%d", &tHeight);
  18             for(int i = 1; i <= tHeight; i++){
  19                 for(int j = 1; j <= i; j++){
  20                     scanf("%d", &tower[i][j]);
  21                 }
  22             }
  23             memset(tmax,0,101*101*4);
  24 
  25             //dp
  26             for(int k = tHeight; k > 0; k--){
  27                 for(int l = 1; l <= k; l++)
  28                     if(k==tHeight)
  29                         tmax[k][l] = tower[k][l];
  30                     else
  31                         tmax[k][l] = tower[k][l] + max(tmax[k+1][l],tmax[k+1][l+1]);
  32             }
  33             printf("%d\n", tmax[1][1]);
  34         }
  35     
  36 
  37     return 0;
  38 }