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

# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param matrix int整型二维数组 the matrix
# @return int整型
#
class Solution:
    def minPathSum(self , matrix: List[List[int]]) -> int:
        # write code here
        r = len(matrix)
        c = len(matrix[0])
        dp = [[0 for j in range(c)] for i in range(r)]
        dp[-1][-1] = matrix[-1][-1]
        # 记录经由该节点 往下走的最小路径和
        for i in reversed(range(r)):
            for j in reversed(range(c)):
                if i == r-1 and j < c-1:
                    dp[i][j] = matrix[i][j] + dp[i][j+1]
                elif i < r-1 and j == c-1:
                    dp[i][j] = matrix[i][j] + dp[i+1][j]
                elif i < r-1 and j < c-1:
                    dp[i][j] = matrix[i][j] + min(dp[i+1][j], dp[i][j+1])
        
        return dp[0][0]