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

一时失言乱红尘 2023-02-12 14:22 17阅读 0赞

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

# 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 时间复杂度 ##

![在这里插入图片描述][20200526141128613.png]  
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\]：

## 3.3 时间复杂度 ##

![在这里插入图片描述][20200526145948175.png]  
O(N)

*  N为元素总数

## 3.4 空间复杂度 ##

O(M ^ 2)

*  M为元素行数

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

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

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

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

[20200526141128613.png]: https://img-blog.csdnimg.cn/20200526141128613.png
[20200526145948175.png]: https://img-blog.csdnimg.cn/20200526145948175.png