題目

給定一個(gè)數(shù)字三角形，找到從頂部到底部的最小路徑和。每一步可以移動(dòng)到下面一行的相鄰數(shù)字上。
** 注意事項(xiàng)
如果你只用額外空間復(fù)雜度O(n)的條件下完成可以獲得加分，其中n是數(shù)字三角形的總行數(shù)。**

樣例
比如，給出下列數(shù)字三角形：

數(shù)字三角形.PNG

從頂?shù)降撞康淖钚÷窂胶蜑?1 ( 2 + 3 + 5 + 1 = 11)。

分析1 （常規(guī)的動(dòng)態(tài)規(guī)劃解法）

類似于前篇最小路徑和的分析，我們假設(shè)到i,j的代價(jià)路徑和為dp[i][j]
那么走到i，j就只有兩種情況，一種是從i-1,j-1過(guò)來(lái)，一種是從i-1,j過(guò)來(lái)。
找到狀態(tài)轉(zhuǎn)移方程：
dp[i][j] = Math.min(dp[i-1][j], dp[i-1][j-1]) + triangle[i][j];
然后我們初始化i=0的dp和i=j的dp，最后就可以利用狀態(tài)轉(zhuǎn)移方程算出結(jié)果

public class Solution {
    /**
     * @param triangle: a list of lists of integers.
     * @return: An integer, minimum path sum.
     */
    public int minimumTotal(int[][] triangle) {
        // write your code here
         //從底往上，把每一行的元素改為其下一行能與之相加的兩個(gè)數(shù)得到的和的最小值
        int row = triangle.length;
        //int col = triangle[row-1].length;
        if(row < 0)
            return row;
        if(row == 1)
            return triangle[0][0];
        int[][] dp = new int[row+1][row+1];
        dp[0][0] = triangle[0][0];
        for(int i=1; i<row; i++) {  
            dp[i][0] = dp[i-1][0]+triangle[i][0];  
        }
        for(int i=1; i<row; i++) {  
            dp[i][i] = dp[i-1][i-1]+triangle[i][i];  
        }
        for(int i=2;i<row;i++)
            for(int j=1;j<i;j++)
                dp[i][j] = Math.min(dp[i-1][j], dp[i-1][j-1]) + triangle[i][j];
        
        int min = dp[row-1][0];
        for(int i=1;i<row;i++)
        {
            if(dp[row-1][i]< min)
                min = dp[row-1][i];
        }
            
        return min;
    }

分析2 （如果你只用額外空間復(fù)雜度O(n)的條件）

從頂部到底部的最小路徑和等于從底部到頂部的最小路徑和 //從倒數(shù)第二層開(kāi)始，從底層到每一層每個(gè)數(shù)字的最小路徑長(zhǎng)度等于，從底層到該層的下層相鄰數(shù)字的最小路徑長(zhǎng)度中的較小值，加上該層該數(shù)字的值。

public class Solution {
    /**
     * @param triangle: a list of lists of integers.
     * @return: An integer, minimum path sum.
     */
    public int minimumTotal(int[][] triangle) {
        // write your code here
         //從底往上，把每一行的元素改為其下一行能與之相加的兩個(gè)數(shù)得到的和的最小值
        int row = triangle.length;
        
        if(row < 1){
            return 0;
        }
        
        if(row == 1){
            return triangle[0][0];
        }
        
        for(int i=row-2;i>=0;i--){
            for(int j=0;j<triangle[i].length;j++){
                int min = Math.min(triangle[i+1][j], triangle[i+1][j+1]) + triangle[i][j];
                triangle[i][j] = min;
            }
        }
        
        return triangle[0][0];
    }
}