# # 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 # # # @param matrix int整型二维数组 the matrix # @return int整型 # class Solution: def minPathSum(self , matrix: List[List[int]]) -> int: # write code here n = len(matrix) # # row m = len(matrix[0]) # # col dp = [[0 for i in range(m)] for j in range(n)] dp[0][0] = matrix[0][0] for i in range(1, m): # # first row dp[0][i] = dp[0][i-1] + matrix[0][i] for i in range(1, n): # # first col dp[i][0] = dp[i-1][0] + matrix[i][0] for i in range(1, n): for j in range(1, m): dp[i][j] = min(dp[i][j-1]+matrix[i][j], dp[i-1][j]+matrix[i][j]) print(dp[-1][-1]) return dp[-1][-1]
一个比较经典的dp问题了,只能朝右走或者朝下走,那么每个位置的值就是当前的值加上左边或上边的最小值