题目：
给定一个三角形，找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。
相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。题目链接
例如，给定三角形：
[ [2], [3,4], [6,5,7], [4,1,8,3] ] 自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。
解法1：常规递归，超时
class Solution {
private:
void findMini(vector<vector<int>>& triangle, int rows, int row, int col, int sum, int& res) {
if (row == rows) {
if (sum < res)
res = sum;
return;
}
findMini(triangle, rows, row+1, col, sum+triangle[row][col], res);
findMini(triangle, rows, row+1, col+1, sum+triangle[row][col], res);
}
public:
int minimumTotal(vector<vector<int>>& triangle) {
int rows = triangle.size();
int res = 0x70000000;
findMini(triangle, rows, 0, 0, 0, res);
return res;
}
};
解法2：自下而上 原地修改削枝至根部
class Solution {
public:
int minimumTotal(vector<vector<int>>& triangle) {
int rows = triangle.size();
if (0 == rows)
return -1;
for (int i = rows-2; i >= 0; i--) //倒数第二行开始，到第一行
for (int j = 0; j <= i; j++)
triangle[i][j] += min(triangle[i+1][j], triangle[i+1][j+1]);//加和下一行下和右下的较小数
return triangle[0][0];
}
};
解法3：从上而下，利用一个辅助数组
class Solution {
public:
int minimumTotal(vector<vector<int>>& triangle) {
int rows = triangle.size();
if (0 == rows)
return -1;
vector<int> line(rows);
line[0] = triangle[0][0];
for (int i = 1; i < rows; i++)
for (int j = i; j >= 0; j--) //从右至左，以防覆盖前面的原数据
if (0 == j)
line[j] += triangle[i][j];
else if (i == j)
line[j] = line[j-1] + triangle[i][j];
else
line[j] = min(line[j-1], line[j]) + triangle[i][j];
for (int i = 1; i < rows; i++) //用line[0]存最小值
if (line[0] > line[i])
line[0] = line[i];
return line[0];
}
};
