题解 | #矩阵的最小路径和#
矩阵的最小路径和
http://www.nowcoder.com/practice/7d21b6be4c6b429bb92d219341c4f8bb
dp大法好
class Solution: def minPathSum(self , matrix ): # write code here n = len(matrix) m = len(matrix[0]) dp = [[-1 for i in range(m)]for i in range(n)] dp[0][0]=matrix[0][0] for i in range(1,n): dp[i][0] = dp[i-1][0]+matrix[i][0] for j in range(1,m): dp[0][j] = dp[0][j-1]+matrix[0][j] for i in range(1,n): for j in range(1,m): dp[i][j] = min(dp[i-1][j],dp[i][j-1])+matrix[i][j] return dp[n-1][m-1]