题目链接：

自下而上，状态转移方程：dp[i][j]=max(dp[i+1][j]+map[i][j],dp[i+1][j+1]+map[i][j]);

1 #include
      
        2 #include
       
         3 const int N=110; 4 using namespace std; 5 int map[N][N],dp[N][N]; 6  7 int main(){ 8     int _case; 9     scanf("%d",&_case);10     while(_case--){11         int n;12         scanf("%d",&n);13         memset(map,0,sizeof(map));14         memset(dp,0,sizeof(dp));15         for(int i=0;i
        
         =0;i--){21             for(int j=0;j<=i;j++){22                 dp[i][j]=max(dp[i+1][j]+map[i][j],dp[i+1][j+1]+map[i][j]);23             }24         }25         printf("%d\n",dp[0][0]);26     }27     return 0;28 }