题意：给出一个三角阵，从第一行第一个数开始，从上到下，每次走数的左下邻或者右下邻，求到最后一行后，经过的数的最大和（1 < 三角阵行数 <= 100，0 <= 三角阵里的数 <= 99）。
设dp[i][j]表示从第i行第j个数开始的最大和，则状态转移方程为：
dp[i][j] = nTriangle[i][j] + max(dp[i + 1][j], dp[i + 1][j + 1]);
滚动数组优化成一维。。
dp[j] = nTriangle[i][j] + max(dp[j], dp[j + 1]);
时间复杂度：O(N ^ 2)
#include <cstdio>
#include <algorithm>using std::max;const int MAXN = 100 + 10;int nTriangle[MAXN][MAXN];
int dp[MAXN];int N;int main()
{while (scanf("%d", &N) == 1){for (int i = 1; i <= N; ++i){for (int j = 1; j <= i; ++j){scanf("%d", &nTriangle[i][j]);}}for (int i = 1; i <= N; ++i){dp[i] = nTriangle[N][i];}for (int i = N - 1; i >= 1; --i){for (int j = 1; j <= i; ++j){dp[j] = nTriangle[i][j] + max(dp[j], dp[j + 1]);}}printf("%d\n", dp[1]);}return 0;
}