三角形最小路径和

来源Leetcode第120题三角形最小路径和

给定一个三角形，找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。

例如，给定三角形：

[
[2],
[3,4],
[6,5,7],
[4,1,8,3]
]
自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。

---

自顶向下的动态规划

首先先确定倒数第二层的最短路径，在依次往上推。
缺点就是用时有点长，用时13ms，击败了6.51%的用户

代码如下：

public int minimumTotal(List<List<Integer>> triangle) {
    if(triangle.size() == 0)
        return 0;
    int minStep = 0;
    for(int i = triangle.size() - 2 ; i>=0 ; i --)
        for(int j = 0 ; j < triangle.get(i).size(); j++) {
            minStep = Math.min(triangle.get(i + 1).get(j),triangle.get(i + 1).get(j + 1)) + triangle.get(i).get(j);
            triangle.get(i).set(j,minStep);
        }
    return triangle.get(0).get(0);
}

O(n)空间复杂度

思路和上一个是一样的，但是就是因为开拓了O(n)的数组，可以大大缩短访问时间，减少了List的get访问次数

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

补充

更新于2020年7月14日，每日一题

可用一维数组缓存中间状态，自底向上搜索，状态转移公式为$ dp[i] = Min(dp[i],dp[i+1]) + list[j][i]$

代码如下：

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