题目：
Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below.
For example, given the following triangle
[
[2],
[3,4],
[6,5,7],
[4,1,8,3]
]
The minimum path sum from top to bottom is 11 (i.e., 2 + 3 + 5 + 1 = 11).
Note:
Bonus point if you are able to do this using only O(n) extra space, where n is the total number of rows in the triangle.
分析：
给定一个三角形，找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。
从最底层往上去找，开辟一个二维数组res，其中res[i][j]记录到达该点时，最小的路径和，状态转移方程是res[i][j] = min(res[i+1][j]+triangle[i][j], res[i+1][j+1]+triangle[i][j])，也就是到达这个位置的最小路径和，等于当前的值加上下一层相邻的最小路径和的较小的值，值得注意的是，数组的形式实际是如下的：
[2],
[3,4],
[6,5,7],
[4,1,8,3]
而不是看起来那样的三角形，注意索引就好。
题中说使用 O(n) 的额外空间，一旦理解了这道题的思路，就很容易做了，开辟一个大小为三角形行数大小的数组，每一次状态更新时，在数组中更新就好。
res[j] = min(res[j]+triangle[i][j], res[j+1]+triangle[i][j]);
程序：
//O(n^2) space
class Solution {
public:
int minimumTotal(vector<vector<int>>& triangle) {
int m = triangle.size();
vector<vector<int>> res(m+, vector<int>(m+, ));
//res[i][j] = min(res[i+1][j]+triangle[i][j], res[i+1][j+1]+triangle[i][j])
for(int i = m-; i >= ; --i)
for(int j = ; j < triangle[i].size(); ++j)
res[i][j] = min(res[i+][j]+triangle[i][j], res[i+][j+]+triangle[i][j]);
return res[][];
}
};
//O(n) space
class Solution {
public:
int minimumTotal(vector<vector<int>>& triangle) {
int m = triangle.size();
vector<int> res(m+, );
//res[j] = min(res[j]+triangle[i][j], res[j+1]+triangle[i][j])
for(int i = m-; i >= ; --i)
for(int j = ; j < triangle[i].size(); ++j)
res[j] = min(res[j]+triangle[i][j], res[j+]+triangle[i][j]);
return res[];
}
};