題目描述

給定一個(gè)三角形triangle，找出自頂向下的最小路徑和。
每一步只能移動(dòng)到下一行中相鄰的結(jié)點(diǎn)上。相鄰的結(jié)點(diǎn)在這里指的是下標(biāo)與“上一層結(jié)點(diǎn)小標(biāo)”相同或者等于“上一層結(jié)點(diǎn)下表+1”的兩個(gè)結(jié)點(diǎn)。也就是說(shuō)，如果正位于當(dāng)前行的下標(biāo)i，那么下一步可以移動(dòng)到下一行的下標(biāo)i或者i+1。

示例

輸入：triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]
輸出：11
解釋：
2
3 4
6 5 7
4 1 8 3
自頂向下的最小路徑和為 11（即，2 + 3 + 5 + 1 = 11）。

思路方法

動(dòng)態(tài)規(guī)劃
在本題中，給定的三角形的行數(shù)為 n，并且第 i 行（從 0 開(kāi)始編號(hào)）包含了 i+1 個(gè)數(shù)。如果將每一行的左端對(duì)齊，那么會(huì)形成一個(gè)等腰直角三角形，如下所示：

[2]
[3,4]
[6,5,7]
[4,1,8,3]

使用動(dòng)態(tài)規(guī)劃法，因?yàn)榈妊切蔚奶厥庑?，所以dp[i][j]有三種情況：
1、也是最容易想到的一種，dp[i][j] = Math.min(dp[i-1][j-1],dp[i-1][j])+triangle.get(i).get(j)
2、當(dāng)處于“等腰直角三角形”的左邊界的時(shí)候，那么dp只有一種來(lái)源：
dp[i][0] = dp[i-1][0]+triangle.get(i).get(0)
3、當(dāng)處于每一行的最右邊的時(shí)候，dp也只有一種來(lái)源：
dp[i][i] = dp[i-1][i-1]+triangle.get(i).get(i)
根據(jù)上面的規(guī)則一直更新到最后一層，再找出最后一層的最小值。

class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        int length  = triangle.size();
        int[][] dp = new int[length][length];
        dp[0][0] = triangle.get(0).get(0);
        for(int i=1;i<length;i++){
            dp[i][0] = dp[i-1][0]+triangle.get(i).get(0);
            for(int j=1;j<i;j++){
                dp[i][j] = Math.min(dp[i-1][j-1],dp[i-1][j])+triangle.get(i).get(j);
            }
            dp[i][i] = dp[i-1][i-1]+triangle.get(i).get(i);
        }
        int minVal = dp[length-1][0];
        for(int i=1;i<length;i++){
            minVal = Math.min(minVal,dp[length-1][i]);
        }
        return minVal;
    }
}

復(fù)雜度分析

• 時(shí)間復(fù)雜度：O(n^2)。n是三角形的行數(shù)。
• 空間復(fù)雜度：O(n^2)。我們需要一個(gè)n*n的二維數(shù)組存放所有的狀態(tài)。