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.
问题描述：给定一个三角形，找到一条从顶部到底部的路径，要求路径上的和值最小，每一步你只能往下一行的相邻位置走下去。
如上面的例子，下面还说，如果只使用O(n)的额外空间更好，n是三角形的行数。
这题是典型的利用动态规划方式思考的问题，设f(i, j)是从第一行到第i行，第j个数字的最小和值，那么f(i, j)要么是从f(i-1, j-1)而来，要么是从f(i-1, j)而来，因此，最优子结构有：
f(i, j) = min(f(i-1, j-1), f(i-1, j)) + triangle[i][j]，通过这种方式，可以得到从第一行到第n行的所有点的最小和值，然后取第n行的最小值即可。
按照通常的方式，这种方法要使用O(n^2)的额外空间，这里，使用一个tmp的额外空间来进行中转，因为下一行的结果只依赖与上一行的结果，所以，程序使用2*n的额外空间。
class Solution {
public:
int minimumTotal(vector > &triangle) {
// IMPORTANT: Please reset any member data you declared, as
// the same Solution instance will be reused for each test case.
if(triangle.size() == 0)
return 0;
vector >::size_type tri_size = triangle.size();
int *min_route = new int[tri_size]();
int *tmp = new int[tri_size]();
int i = 0, j = 0;
for(i = 0; i != tri_size; ++i) {
for(j = 0; j != triangle[i].size(); ++j) {
if(i == 0) {
tmp[0] = triangle[0][0];
}
else if(j == 0) {
tmp[j] = min_route[j] + triangle[i].at(j);
}
else if(j == triangle[i].size()-1) {
tmp[j] = min_route[j-1] + triangle[i].at(j);
}
else {
tmp[j] = min(min_route[j-1], min_route[j]) + triangle[i].at(j);
}
}
copy(tmp, tmp+tri_size, min_route);
}
int min_tot = *min_element(min_route, min_route+tri_size);
delete [] min_route;
delete [] tmp;
return min_tot;
}
};