LeetCode题解：三角形最小路径和

题目描述

给定一个三角形triangle，找出自顶向下的最小路径和。
每一步只能移动到下一行中相邻的结点上。相邻的结点在这里指的是下标与“上一层结点小标”相同或者等于“上一层结点下表+1”的两个结点。也就是说，如果正位于当前行的下标i，那么下一步可以移动到下一行的下标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）。

思路方法

动态规划
在本题中，给定的三角形的行数为 n，并且第 i 行（从 0 开始编号）包含了 i+1 个数。如果将每一行的左端对齐，那么会形成一个等腰直角三角形，如下所示：

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

使用动态规划法，因为等腰三角形的特殊性，所以dp[i][j]有三种情况：
1、也是最容易想到的一种，dp[i][j] = Math.min(dp[i-1][j-1],dp[i-1][j])+triangle.get(i).get(j)
2、当处于“等腰直角三角形”的左边界的时候，那么dp只有一种来源：
dp[i][0] = dp[i-1][0]+triangle.get(i).get(0)
3、当处于每一行的最右边的时候，dp也只有一种来源：
dp[i][i] = dp[i-1][i-1]+triangle.get(i).get(i)
根据上面的规则一直更新到最后一层，再找出最后一层的最小值。

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;
    }
}

复杂度分析

• 时间复杂度：O(n^2)。n是三角形的行数。
• 空间复杂度：O(n^2)。我们需要一个n*n的二维数组存放所有的状态。