leetcode筆記：Triangle

leetcode筆記：Triangle

一. 題目描述

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