一. 題目描述
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.
二. 題目分析
使用動態規劃來完成。設從頂部到第i層的第k個頂點的最小路徑長度表示為f(i, k)，則f(i, k) = min{f(i-1,k), f(i-1,k-1)} + d(i, k)，其中d(i, k)表示原來三角形數組裡的第i行第k列的元素。則可以求得從第一行到最終到第length-1行第k個元素的最小路徑長度，最後再比較第length-1行中所有元素的路徑長度大小，求得最小值。
這裡需要注意邊界條件，即每一行中的第一和最後一個元素在上一行中只有一個鄰居。而其他中間的元素在上一行中都有兩個相鄰元素。
三. 示例代碼
class Solution {
public:
int minimumTotal(vector > &triangle) {
vector< vector >::size_type length = triangle.size();
if(length == 0){
return 0;
}
int i, j;
for(i=1;i::size_type length_inner = triangle[i].size();
for(j=0;j
