题目大意：从第一行走到最后一行，走过的地方和就累计往下。问最大的结果为多少。
解题思路：第一种dfs遍历超时，第二种dfs中将较大的值保存，第三种从底下往上走。
关于这题是在博客看的http://blog.csdn.net/baidu_28312631/article/details/47418773
第二种ac代码：
#include <iostream>
#include <cstring>
using namespace std;
int n, D[105][105], maxs[105][105];
int max(int a, int b)
{
return a > b?a:b;
}
int maxsum(int a, int b)
{if (maxs[a][b] != -1)return maxs[a][b];if (a == n)maxs[a][b] = D[a][b];elsemaxs[a][b] = D[a][b] + max(maxsum(a+1, b), maxsum(a+1, b+1));
return maxs[a][b];
}
int main()
{while (scanf("%d", &n)!=EOF){memset(maxs, -1, sizeof(maxs));for (int i=0; i<n; i++)for (int j=0; j<=i; j++)scanf("%d", &D[i][j]);maxsum(0, 0);printf("%d\n", maxs[0][0]);}
return 0;
}
第三种ac代码：
#include <iostream>
#include <algorithm>
using namespace std;
int n, D[105][105], maxs[105];
int main()
{while (scanf("%d", &n)!=EOF){for (int i=0; i<n; i++)for (int j=0; j<=i; j++)scanf("%d", &D[i][j]);for (int i=0; i<n; i++)maxs[i] = D[n-1][i];for (int i=n-2; i>=0; i--)for (int j=0; j<=i; j++)maxs[j] = D[i][j] + max(maxs[j], maxs[j+1]);printf("%d\n", maxs[0]);}
return 0;
}