时间限制：2 sec
空间限制：256 MB
问题描述给定一个高度为 n 的“数字三角形”，其中第 i 行（1<=i<=n）有 i 个数。（例子如下图所示）
初始时，你站在“数字三角形”的顶部，即第一行的唯一一个数上。每次移动，你可以选择移动到当前位置正下方或者当前位置右下方的位置上。即如果你在 (i,j)（表示你在第i行从左往右数第j个数上，下同），你可以选择移动到 (i+1,j) 或 (i+1,j+1)。
你想让你经过的所有位置（包括起点和终点）的数字总和最大。求这个最大值。
输入格式第一行一个正整数 n，表示数字三角形的大小。
第 2 行到第 n+1 行，第 i+1 行为 i 个用空格隔开的非负整数，描述数字三角形的第 i 行。
输出格式一行一个整数，表示经过路径上数的最大总和。
样例输入4
1
2 3
4 5 6
7 8 9 10
样例输出20
样例解释不停地向右下走即可。
提示[如果我们使用搜索算法，我们会在搜索时记录哪些信息呢？]
[当前到达的点的坐标、当前经过路径上数的总和！]
[总和显然是越大越好！]
[于是可以设计出状态：dp[i][j] 表示走到坐标为 (i,j) 的点时的最大总和。]
[很容易就可以设计出状态转移方程啦！]
一. 伪代码 二. 具体实现（C++）
#include <bits/stdc++.h>
using namespace std;
// ================= 代码实现开始 =================
//dp:用于动态规划的数组，d[i][j]表示要走到第i行第j列能得到最大数字总和
vector<vector<int>> dp;
// 本函数计算答案（最大经过位置数字总和）
// n：描述数字三角形大小，意义同题目描述
// a：描述整个数字三角形，第 i 行的第 j 个数存放在 a[i][j]
// 中（你需要特别注意的是，所有下标均从 1 开始，也就是说下标为 0 的位置将存放无效信息）
// 返回值：最大经过位置数字总和
int getAnswer(int n, vector<vector<int>> a) {
dp.resize(n+1);
for(int i=0; i<=n; ++i)
dp[i].resize(i+2);
for(int i = 1; i <= n; ++i)
for(int j = 1; j<=i; ++j)
dp[i][j] = max(dp[i-1][j-1],dp[i-1][j])+a[i][j];//用左上角和正上方的dp值更新
int ans = 0;
for(int i=1; i<=n; ++i)
ans = max(ans, dp[n][i]);//求最大的数字之和
return ans;
}
// ================= 代码实现结束 =================