算法-动态规划-三角形最小路径和算法-动态规划-三角形最小路径和1 题目概述2 动态规划-自顶向下3 动态规划-自底向上

133 阅读 0 评论 88 点赞

我是靠谱客的博主端庄摩托，这篇文章主要介绍算法-动态规划-三角形最小路径和算法-动态规划-三角形最小路径和1 题目概述2 动态规划-自顶向下3 动态规划-自底向上，现在分享给大家，希望可以做个参考。

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
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 代码

复制代码

// 最后一行的列数
        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];
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
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]：

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
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)

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

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

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

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
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内容请搜索靠谱客的其他文章。

本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。

本文分类：算法
浏览次数：133 次浏览
发布日期：2023-11-22 22:10:02
本文链接：https://www.kaopuke.com/article/k-p-k_13_u_23_o_10_fx_13__23_ky.html

算法-动态规划-三角形最小路径和算法-动态规划-三角形最小路径和1 题目概述2 动态规划-自顶向下3 动态规划-自底向上

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

1 题目概述

1.1 题目出处

1.2 题目描述

2 动态规划-自顶向下

2.1 思路

2.2 代码

2.3 时间复杂度

2.4 空间复杂度

3 动态规划-自底向上

3.1 思路

3.2 代码

3.3 时间复杂度

3.4 空间复杂度

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

最后

评论列表共有 0 条评论

发表评论取消回复

算法-动态规划-三角形最小路径和算法-动态规划-三角形最小路径和1 题目概述2 动态规划-自顶向下3 动态规划-自底向上

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

1 题目概述

1.1 题目出处

1.2 题目描述

2 动态规划-自顶向下

2.1 思路

2.2 代码

2.3 时间复杂度

2.4 空间复杂度

3 动态规划-自底向上

3.1 思路

3.2 代码

3.3 时间复杂度

3.4 空间复杂度

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

最后

相关文章

评论列表共有 0 条评论

发表评论 取消回复

微信扫一扫：分享

发表评论取消回复