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).
思路：
自底向上，存当前数字加下面两个中比较小的数字，最后顶上的数字就是答案了。不难，直接AC
class Solution {
public:
int minimumTotal(vector<vector<int> > &triangle) {
vector<vector<int>> data(triangle.size(), vector<int>());
data[data.size() - ] = triangle[triangle.size() - ];
for(int i = triangle.size() - ; i >= ; i--)
{
for(int j = ; j < triangle[i].size(); j++)
{
int min = (data[i + ][j] < data[i + ][j + ]) ? data[i + ][j] : data[i + ][j + ];
data[i].push_back(min + triangle[i][j]);
}
}
return data[][];
}