题解 | #矩阵的最小路径和#

矩阵的最小路径和，动态规划，时间O(mn)，空间O(m)

动态规划的核心：初始状态+状态转移方程

class Solution:
    def minPathSum(self , matrix: List[List[int]]) -> int:
        m, n = len(matrix), len(matrix[0])
        dp = [0]
        for i in range(n):          # 第一行状态
            dp.append(dp[i]+matrix[0][i])
        dp[0] = 50001               # 给一个足够大值值，保证不会从占状态过来
        for i in range(1, m):
            for j in range(n):
                dp[j+1] = min(dp[j+1], dp[j])+matrix[i][j]    # 两个途径转换，取较小者
        return dp[-1]