【算法面试通关40讲】46 - 面试题：三角形的最小路径和Leetcode-120. 三角形最小路径和

104 阅读 0 评论 69 点赞

我是靠谱客的博主闪闪烤鸡，这篇文章主要介绍【算法面试通关40讲】46 - 面试题：三角形的最小路径和Leetcode-120. 三角形最小路径和，现在分享给大家，希望可以做个参考。

Leetcode-120. 三角形最小路径和

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

例如，给定三角形：

复制代码

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

自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。

说明：

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

解法：1. 递归回溯，使用自顶向下的方法，走到最顶部的最短路径等于左右两条路径的最小值，一直递归到最后即可，同样会有重复的问题，可以用记忆化解决。 2. 使用dp，使用自底向上的方法，首先需要定义dp[i, j]的状态，dp[i, j]的含义是到达i，j位置时所用的最小消耗，接下来定义dp方程，dp[i,j] = min(dp[i+1, j], dp[i+1, j+1]) + trangle[i, j]，含义就是i，j位置的值等于下面一层左右路径的最小值，加上本身带有的值，然后定义初始值，最下面一层的dp值就是本身的trangle值。时间复杂度和空间复杂度都是O（MN）

Java
先写一个递归+记忆化方法

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        int[][] memory = new int[triangle.size()][triangle.get(triangle.size()-1).size()];
        return this.dfs(triangle, memory, 0, 0);
    }
    public int dfs(List<List<Integer>> triangle, int[][] memory, int i, int j) {
        if (i==triangle.size()-1)
            return triangle.get(i).get(j);
        else if (memory[i][j]==0) {
            int tmp = triangle.get(i).get(j) + Math.min(this.dfs(triangle, memory, i+1, j), this.dfs(triangle, memory, i+1, j+1));
            memory[i][j]=tmp;
        }
        return memory[i][j];
    }
}

再写一个递推方法，大家可以比较一下不同，时间复杂度O（MN），空间复杂度O（1），但是改变了原数组

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        for (int i=triangle.size()-2;i>=0;i--) {
            for (int j=0;j<triangle.get(i).size();j++) {
                int tmp = triangle.get(i).get(j) + Math.min(triangle.get(i+1).get(j),triangle.get(i+1).get(j+1));
                triangle.get(i).set(j, tmp);
            }
        }
        return triangle.get(0).get(0);
    }
}

时间复杂度O（MN），没有改变原数组，空间复杂度O（N），如果要刷运行速度排名，请将res由list换为数组

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        if (triangle == null || triangle.isEmpty())
            return 0;
        List<Integer> res = triangle.get(triangle.size()-1);
        for (int i=triangle.size()-2;i>=0;i--) {
            for (int j=0;j<triangle.get(i).size();j++) {
                int tmp = triangle.get(i).get(j) + Math.min(res.get(j),res.get(j+1));
                res.set(j, tmp);
            }
        }
        return res.get(0);
    }
}

Python

复制代码

1
2
3
4
5
6
7
8
9
class Solution:
    def minimumTotal(self, triangle: List[List[int]]) -> int:
        if not triangle :return 0
        res = triangle[-1]
        for i in range(len(triangle)-2,-1,-1):
            for j in range(len(triangle[i])):
                res[j] = triangle[i][j] + min(res[j], res[j+1])
        return res[0]