三角形最小路径和：经典的动态规划题目
给定一个三角形 triangle ，找出自顶向下的最小路径和。
每一步只能移动到下一行中相邻的结点上。相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。也就是说，如果正位于当前行的下标 i ，那么下一步可以移动到下一行的下标 i 或 i + 1 。
示例 1：
输入：triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]
输出：11
解释：如下面简图所示：
2
3 4
6 5 7
4 1 8 3
自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。
示例 2：
输入：triangle = [[-10]]
输出：-10
动态规划解法：
使用内存占用较大的常规动态规划方法，需要注意，实际遍历过程中，三角形各个值的坐标与直观上的三角形并不相同（相当于从看起来的居中到遍历过程中实际的居左）：
triangle:
2 ----> 2
3 4 ----> 3 4
6 5 7 ----> 6 5 7
4 1 8 3 ----> 4 1 8 3
（1）定义二位dp数组，行数为三角形行数 triangle.size()，列数为三角形最后一行的大小 triangle[triangle.size() - 1].size()；
（2）只需要初始化 dp[0][0]，后续的值依次从上一层的 dp 数组对应位置计算得到；
（3）对于 dp 数组中的每一行，需要分成三种情况：首先，该行最左边位置只能由上一行最左边的值加该位置的值得到，即三角形左斜边的这一条路径；其次，同理，该行最右边位置只能由上一行最右边的值加该位置的值得到，即三角形右斜边的这一条路径；最后，对于中间部分的 dp[i][j]，从上一行的 dp[i - 1][j - 1] 和 dp[i - 1][j] 选择小的值，加三角形本位置的值得到，由上述的实际遍历过程中 triangle 的分布易得。
（4）最终的结果为 dp 数组最后一行的最小值。
class Solution {
public:
int minimumTotal(vector<vector<int>>& triangle) {
int n = triangle.size();
vector<vector<int>> dp(n, vector<int>(triangle[n - 1].size(), 0));
dp[0][0] = triangle[0][0];
for(int i = 1; i < n; i++){
dp[i][0] = dp[i - 1][0] + triangle[i][0];
for(int j = 1; j < triangle[i].size() - 1; j++){
dp[i][j] = min(dp[i - 1][j - 1], dp[i - 1][j]) + triangle[i][j];
}
dp[i][i] = dp[i - 1][i - 1] + triangle[i][i];
}
int ans = dp[n - 1][0];
for(int j = 1; j < triangle[n - 1].size(); j++){
if(dp[n - 1][j] < ans)
ans = dp[n - 1][j];
}
return ans;
}
};使用空间优化后的动态规划方法：无论是从上到下遍历还是从下到上遍历，每一行 dp 数组的值只与其前一行 dp 数组的值有关，只需定义一维 dp 数组用于存放每一行各个位置的最小路径累积值；同时，从下到上遍历的过程更为简便。
从三角形最后一行依次向第一行遍历，dp[j] 为原 dp 数组中的 dp[j] 与 dp[j + 1] 中较小值加三角形对应位置的值，最终直接返回第一行的 dp[0] 即可。
其中，dp 数组初始化为三角形最后一行大小加1，这是为了在 i = triangle.size() - 1，即最后一行各数的遍历过程中，处理最后一个数时不越界。
class Solution {
public:
int minimumTotal(vector<vector<int>>& triangle) {
vector<int> dp(triangle.size() + 1, 0);
for(int i = triangle.size() - 1; i >= 0; i--){
for(int j = 0; j < triangle[i].size(); j++){
dp[j] = min(dp[j], dp[j + 1]) + triangle[i][j];
}
}
return dp[0];
}
};