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

同样是最经典最简单的dp了，设dp[i][j]为到达地i行第j列时的最短路径，则状态转移方程为：

$dp[i][j]=min\{dp[i-1][j]+matrix[i][j],dp[i][j-1]+matrix[i][j]\}dp[i][j]=min\backslash \{dp[i-1][j]+matrix[i][j]\; ,\; dp[i][j-1]+matrix[i][j]\backslash \}$

有了状态转移方程后就没问题了，代码如下：

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param matrix int整型二维数组 the matrix
# @return int整型
#
import copy
class Solution:
    def minPathSum(self , matrix) -> int:
        # write code here
        # 初始化dp矩阵
        dp = copy.deepcopy(matrix)
        # 初始化第0行和第0列
        for j in range(1 , len(matrix[0])):
            dp[0][j] = dp[0][j-1]+matrix[0][j]
        for i in range(1 , len(matrix)):
            dp[i][0] = dp[i-1][0] + matrix[i][0]
        # 更新dp矩阵
        for i in range(1,len(matrix)):
            for j in range(1,len(matrix[0])):
                dp[i][j] = min(dp[i-1][j]+matrix[i][j] , dp[i][j-1]+matrix[i][j])
        return dp[-1][-1]

matrix = [[1,3,5,9],[8,1,3,4],[5,0,6,1],[8,8,4,0]]
print(Solution().minPathSum(matrix))