矩阵的最小路径和

矩阵的最小路径和_牛客题霸_牛客网

问题简述

给定一个 n * m 的矩阵 a，从左上角开始每次只能向右或者向下走，最后到达右下角的位置，路径上所有的数字累加起来就是路径和，输出所有的路径中最小的路径和。

思路

• 定义 dp(i,j) 表示到达 m[i][j] 最短距离；

• 递推公式：dp(i,j) = m[i][j] + min(dp(i-1,j), dp(i,j-1))；

• 初始化：

  • dp(i,0)=sum(m[:i][]0)

  • dp(0,j)=sum(m[0][:j])；

递归写法

class Solution:
    def minPathSum(self, matrix: List[List[int]]) -> int:
        
        import sys
        sys.setrecursionlimit(100000)
        from functools import lru_cache
        
        @lru_cache(maxsize=None)
        def dfs(i, j):
            if i == 0 and j == 0: return matrix[i][j]
            if i == 0: return sum(matrix[i][j] for j in range(j + 1))
            if j == 0: return sum(matrix[i][j] for i in range(i + 1))
            
            return matrix[i][j] + min(dfs(i - 1, j), dfs(i, j - 1))
        
        m, n = len(matrix), len(matrix[0])
        return dfs(m - 1, n - 1)

迭代写法（略）