算法-动态规划-三角形最小路径和

1 题目概述

1.1 题目出处

https://leetcode-cn.com/problems/triangle/

1.2 题目描述

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

相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。

例如，给定三角形：

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

说明：

如果你可以只使用 O(n) 的额外空间（n 为三角形的总行数）来解决这个问题，那么你的算法会很加分。

2 动态规划-自顶向下

2.1 思路

设dp[i][j] 为 i行j列的最小路径和，则dp[i][j] = Math.min(dp[i-1][j],dp[i-1][j-1])。其中i为行号，j为列号，都从零开始。

我们自顶向下开始进行动态规划计算。

先计算dp[0][0] = triangle.get(0).get(0)，还需要对每行的首元素和尾元素单独特殊处理。

2.2 代码

class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        int result = 0;
        if(triangle == null || triangle.size() == 0){
            return result;
        }
        if(triangle.size() == 1){
            return triangle.get(0).get(0);
        }
        // 设dp[i][j] 为 i行j列的最小路径和
        // 则dp[i][j] = Math.min(dp[i-1][j],dp[i-1][j-1])
        // 最后一行的列数
        int columns = triangle.get(triangle.size() - 1).size();
        int[][] dp = new int[triangle.size()][columns];
        dp[0][0] = triangle.get(0).get(0);
        // 找出第2行到倒数第二行的最小路径和
        for(int i = 1; i < triangle.size() - 1; i++){
            List<Integer> columnList = triangle.get(i);
            dp[i][0] = dp[i-1][0] + columnList.get(0); 
            dp[i][columnList.size() - 1] = dp[i-1][columnList.size() - 2] + columnList.get(columnList.size() - 1); 
            for(int j = 1; j < columnList.size() - 1; j++){
                dp[i][j] = Math.min(dp[i - 1][j], dp[i - 1][j - 1]) + columnList.get(j);
            }
        }
        // 找出最后一行的最小路径和即可
        int min = Integer.MAX_VALUE;
        int lastRow = triangle.size() - 1;
        List<Integer> lastColumnList = triangle.get(lastRow);
        min = Math.min(min, dp[lastRow-1][0] + lastColumnList.get(0)); 
        min = Math.min(min, dp[lastRow-1][lastColumnList.size() - 2] + lastColumnList.get(lastColumnList.size() - 1)); 

        for(int j = 1; j < lastColumnList.size() - 1; j++){
            min = Math.min(min, Math.min(dp[lastRow - 1][j], dp[lastRow - 1][j - 1]) + lastColumnList.get(j));
        }

        return min;
    }
}

2.3 时间复杂度

O(N)

• N为元素总数

2.4 空间复杂度

O(M ^ 2)

• M为元素行数

3 动态规划-自底向上

3.1 思路

上面自顶向下思路中需要单独处理很多特殊情况，比较麻烦，容易写错。

现在考虑自底向上的动态规划算法：
设dp[i][j] 为 i行j列的最小路径和，则dp[i][j] = Math.min(dp[i-1][j],dp[i-1][j-1])。其中i为行号，j为列号，都从零开始。

先计算尾行，显然每个dp值就是当前元素的值。

然后开始往上逐层计算。

最后返回定点dp[0][0]即可，省去了特殊值处理。

3.2 代码

class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        int result = 0;
        if(triangle == null || triangle.size() == 0){
            return result;
        }
        if(triangle.size() == 1){
            return triangle.get(0).get(0);
        }
        // 设dp[i][j] 为 i行j列的最小路径和
        // 则dp[i - 1][j] = Math.min(dp[i][j], dp[i][j+1]) + triangle.get(i - 1).get(j);

        // 最后一行的列数
        int columns = triangle.get(triangle.size() - 1).size();
        int[][] dp = new int[triangle.size()][columns];

        // 先初始化最后一行   
        int lastRow = triangle.size() - 1;
        List<Integer> lastColumnList = triangle.get(lastRow);
        for(int j = 0; j < lastColumnList.size(); j++){
            dp[lastRow][j] = lastColumnList.get(j);
        }
        
        // 从最后一行开始往上递推
        for(int i = triangle.size() - 1; i > 0; i--){
            List<Integer> columnList = triangle.get(i); 
            for(int j = 0; j < columnList.size() - 1; j++){
                dp[i - 1][j] = Math.min(dp[i][j], dp[i][j+1]) + triangle.get(i - 1).get(j);
            }
        }

        // 返回首行元素即可
        return dp[0][0];
    }
}

上面还是要处理特殊的最后一行，那么我们虚拟出一行值全为0的尾行，并每次考虑dp[i][j] = Math.min(dp[i+1][j], dp[i+1][j+1]) + triangle.get(i).get(j);，且从真实尾行递推到首行，不用特殊考虑任何行，最后仍然返回dp[0][0]：

class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        int result = 0;
        if(triangle == null || triangle.size() == 0){
            return result;
        }
        if(triangle.size() == 1){
            return triangle.get(0).get(0);
        }
        // 设dp[i][j] 为 i行j列的最小路径和
        // 则dp[i][j] = Math.min(dp[i+1][j], dp[i+1][j+1]) + triangle.get(i).get(j);

        // 最后一行的列数
        int columns = triangle.get(triangle.size() - 1).size();
        int[][] dp = new int[triangle.size() + 1][columns + 1];
        
        // 从真实的最后一行开始往上递推
        for(int i = triangle.size() - 1; i >= 0; i--){
            List<Integer> columnList = triangle.get(i); 
            for(int j = 0; j < columnList.size(); j++){
                dp[i][j] = Math.min(dp[i+1][j], dp[i+1][j+1]) + triangle.get(i).get(j);
            }
        }

        // 返回首行元素即可
        return dp[0][0];
    }
}

3.3 时间复杂度

O(N)

• N为元素总数

3.4 空间复杂度

O(M ^ 2)

• M为元素行数

3.5 优化空间复杂度为O(N)

仔细看前述代码，发现其实每个元素会使用两次：

1. 计算j - 1列的上一行元素最小路径和
2. 计算同列的上一行元素最小路径和

于是可以在结算完同列上一行元素后，结果存于同一位置！这样就能达到O(N)空间复杂度了。

class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        int result = 0;
        if(triangle == null || triangle.size() == 0){
            return result;
        }
        if(triangle.size() == 1){
            return triangle.get(0).get(0);
        }
        // 设dp[i][j] 为 i行j列的最小路径和
        // 则dp[i][j] = Math.min(dp[i-1][j],dp[i-1][j-1])

        // 最后一行的列数
        int columns = triangle.get(triangle.size() - 1).size();
        // O(N)复杂度，可复用
        int[] dp = new int[columns + 1];
        
        // 从真实的最后一行开始往上递推
        for(int i = triangle.size() - 1; i >= 0; i--){
            List<Integer> columnList = triangle.get(i); 
            for(int j = 0; j < columnList.size(); j++){
                dp[j] = Math.min(dp[j], dp[j+1]) + triangle.get(i).get(j);
            }
        }

        // 返回首行元素即可
        return dp[0];
    }
}

最后

以上就是端庄摩托为你收集整理的算法-动态规划-三角形最小路径和算法-动态规划-三角形最小路径和1 题目概述2 动态规划-自顶向下3 动态规划-自底向上的全部内容，希望文章能够帮你解决算法-动态规划-三角形最小路径和算法-动态规划-三角形最小路径和1 题目概述2 动态规划-自顶向下3 动态规划-自底向上所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。