HDU 2084 数塔 动态规划

解题报告：

题目大意：给定一个有N层的数塔，数塔的第i层有i个数，从数塔的第一层出发，每次只能经过相邻的两条路，求走到最底层时走过的那条路线上的数的和最大是多少？

典型的动态规划，一看到这题，毫不犹豫的用了递归写，测试也过了，但交上去就WA了，才知道，递归调用函数是很花时间的，后来改成直接用for循环，46s就过了。

递归的公式是map[i][j]+=(map[i+1][j]>map[i+1][j+1]? map[i+1][j]:map[i+1][j+1]);就是说当我现在在第i层的第j个数的时候，这个位置可以由第i+1层第j个或者第i+1层第j+1个得到，这就比较一下，这两种走法，哪种走法的和大一点就选择哪一种走法，这样最后返回map[1][1]就是我们要的最大的和。

#include<cstdio>
int map[105][105],T,N;
int dfs() {
    for(int i=N-1;i>=1;--i)
    for(int j=1;j<=i;++j)
    map[i][j]+=(map[i+1][j]>map[i+1][j+1]? map[i+1][j]:map[i+1][j+1]);
    return map[1][1];
}
int main() {
    scanf("%d",&T);
    while(T--) {
        scanf("%d",&N);
        for(int i=1;i<=N;++i)
        for(int j=1;j<=i;++j)
        scanf("%d",&map[i][j]);
        printf("%d\n",dfs());
    }
    return 0;
}