经典问题了，题意我就不叙述了（题目是中文的~）
分析：dp[i][j]表示在第i行第j个位置上能取得的最大和，那么要从最后一行开始算起，到塔顶结束：dp[i][j] = a[i][j]+max(dp[i+1][j], dp[i+1][j+1]), 边界条件是dp[n][j] = a[n][j];
代码：
View Code
1 #include <stdio.h> 2 #include <iostream> 3 using namespace std; 4 #define DEBUG 5 const int MAXN = 100 + 5; 6 int a[MAXN][MAXN], dp[MAXN][MAXN]; 7 int max(int a, int b){ 8 return a>b?a:b; 9 } 10 int main(){ 11 #ifndef DEBUG 12 freopen("in.txt", "r", stdin); 13 #endif 14 int cas; 15 scanf("%d", &cas); 16 while(cas--){ 17 int n; 18 scanf("%d", &n); 19 int i, j; 20 for(i=1; i<=n; i++) 21 for(j=1; j<=i; j++) 22 scanf("%d", &a[i][j]); 23 for(j=1; j<=n; j++) dp[n][j] = a[n][j]; 24 for(i=n-1; i>=1; i--) 25 for(j=1; j<=n; j++) 26 dp[i][j] = a[i][j] + max(dp[i+1][j], dp[i+1][j+1]); 27 printf("%d\n", dp[1][1]); 28 } 29 return 0; 30 }
