此为历史版本和 IPFS 入口查阅区,回到作品页
土豆炒青椒
IPFS 指纹 这是什么

作品指纹

「谷歌」64 ~ 最小的路径和

土豆炒青椒
·
旧题新做 时做时新 🤪

基本信息

  • 题号:64

  • 题厂:谷歌

  • 难度系数:中


已知一个 m * n 的矩阵,矩阵格子里有一些数字。问从左上角走到有下角,最小的路径和是多少?

(只能往右走,或者往下走)

如上图所示,从左上角到右下角的最小路径和为 1 → 3 → 1 → 1 → 1,加起来就是 7……

解题思路

欲解此题,需要具备一些 recursive (递归)和 「动态规划」(dynamic programming)的基础……

默认具备「递归」思想和「动态规划」思想后,再来进行化繁为简初步分析。

1 * 1 的格子

显而易见,只有一种走法,或者根本就不用走,直接返回格子数本身——1.

1 * n 格子

当矩阵只有一行时,还是只有一种走法,4 - 2 - 1,走法。这里运用递归思路,我从 4 走到 2,没走完,接着走直到走到 1 可以结束程序,路径和为 4 + 2 + 1 = 7.

n * 1 格子

此案例和一行矩阵思路类似,只有一种走法。1 + 1 + 1 = 3

多重走法

只有行和列同时大于 1 时,才可能出现多种走法。例如 5 - 1 - 1, 5 + 1 + 1 = 7 和 5 - 2 - 1, 5 + 2 + 1 = 8. 择优后选择 5 - 1 - 1 走法,最小路径和为 7.


经过以上分析,我们可以从基本款(1 * 1 矩阵)入手,不断计算所有走法,然后再择优返回所有走法的最小值,即可完成任务。

以上思路可以通过「递归」来实现代码

class Solution:
    def minPathSum(self, grid: List[List[int]]) -> int:
        
        ROW, COL = len(grid), len(grid[0])
        
        # 创建递归方法
        def recursion(i, j):
            # 当行列为 1 时,返回格子本身(只有一种走法)
            if i == j == 0:
                return grid[i][j]
            
            # 当只有 1 行时,只有一种走法,返回所有格子和
            if i == 0:
                return grid[i][j] + recursion(i, j - 1)

            # 当只有 1 列时,只有一种走法,返回所有格子和
            if j == 0:
                return grid[i][j] + recursion(i - 1, j)

            # 当有 1+ 行 和 1+ 列时,我们选取较小的那一款走法,递归计算
            return grid[i][j] + min(recursion(i - 1, j), recursion(i, j - 1))

        return recursion(ROW - 1, COL - 1)

以上思路无逻辑错误,但复杂度太高,无法满足题目需求。所以需要优化……

代码超时

根据默认解题经验,递归的最优解一般就是动态规划。动态规划的原理和递归有类似之处:都是化繁为简,从最基础模式开始思考,逐步发展找出规律(后面的计算可以从基本模式发展演算),类似于高中数学等差数列找规律再总结公式的套路……

那么本题的规律也很容易发现:格子只能从上边或者左边发展过来。如果从上走过来小,就择优选择从上走;如果从左走过来小,那就择优从左走。而上一步又可以不断往前知道 1 * 1 只有一个格子时。而在这个过程中,我们可以记录走到下一步需要的路径和,当有多种走法的时候就择优累加即可,达到简化代码和复杂度的作用。

class Solution:
    def minPathSum(self, grid: List[List[int]]) -> int:
        
        ROW, COL = len(grid), len(grid[0])
        # 创建一个和题目已知矩阵相同的矩阵,用于记录走到该格子的路径值
        path_grid = [[0] * COL for _ in range(ROW)]
        # 初始化第一个格子
        path_grid[0][0] = grid[0][0]

        # 初始第一行
        for c in range(1, COL):
            path_grid[0][c] = path_grid[0][c - 1] + grid[0][c]
        # 初始第一列
        for r in range(1, ROW):
            path_grid[r][0] = path_grid[r - 1][0] + grid[r][0]
        # 根据初始值,计算后续发展
        for r in range(1, ROW):
            for c in range(1, COL):
                path_grid[r][c] = grid[r][c] + min(path_grid[r - 1][c], path_grid[r][c -1])
        
        return path_grid[ROW - 1][COL - 1]

达成以上动态规划后,我们可以在此基础上做进一步空间复杂度优化:

class Solution:
    def minPathSum(self, grid: List[List[int]]) -> int:
        
        ROW, COL = len(grid), len(grid[0])
        base = [0] * COL
        
        for i in range(len(base)):
            if i == 0:
                base[i] = grid[0][i]
            else:
                base[i] = base[i - 1] + grid[0][i]

        for r in range(1, ROW):
            for c in range(COL):
                if c == 0:
                    base[c] += grid[r][c]
                else:
                    base[c] = grid[r][c] + min(base[c - 1], base[c])

        return base[COL - 1]

Constraints

  • m == grid.length

  • n == grid[i].length

  • 1 <= m, n <= 200

  • 0 <= grid[i][j] <= 200


测试

  • m = n = 1 时

  • 当只有 1 列时

  • 当只有 1 行时

  • 当有多行多列时

  • 当 m = n = 200 时,测试代码有效度

  • ……


Big O

时间复杂度:O(m * n)

空间复杂度: O(n)


总结

  • 这类题可以划归为「矩阵 + 动态规划」递归题型,它们拥有相似的模板和相同的套路

  • 通过比较「递归」模板和「动态规划」模板的异同,理解如何通过「动态规划」达到最优解

  • 相似题型:62, 63, 174

CC BY-NC-ND 4.0 授权