hdu2084数塔

经典问题了，题意我就不叙述了（题目是中文的~）

分析：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];

代码：

#include <stdio.h>
#include <iostream>
using namespace std;
#define DEBUG
const int MAXN = 100 + 5;
int a[MAXN][MAXN], dp[MAXN][MAXN];
int max(int a, int b){
    return a>b?a:b;
}
int main(){
#ifndef DEBUG
    freopen("in.txt", "r", stdin);
#endif
    int cas;
    scanf("%d", &cas);
    while(cas--){
        int n;
        scanf("%d", &n);
        int i, j;
        for(i=1; i<=n; i++)
            for(j=1; j<=i; j++)
                scanf("%d", &a[i][j]);
        for(j=1; j<=n; j++) dp[n][j] = a[n][j];
        for(i=n-1; i>=1; i--)
            for(j=1; j<=n; j++)
                dp[i][j] = a[i][j] + max(dp[i+1][j], dp[i+1][j+1]);
        printf("%d\n", dp[1][1]);
    }
    return 0;
}