算法刷题Day30

题目链接

描述

解题思路

考点：动态规划

1. dp[i][j]表示当前坐标的最小路径和
2. dp初始化
3. 状态转移：
   dp[i][j] = matrix[i][j] + min(dp[i-1][j],dp[i][j-1]) 比较正上方和正左方的路径和哪个小。取小的那条路

代码

import copy
class Solution:def minPathSum(self , matrix: List[List[int]]) -> int:m = len(matrix)n = len(matrix[-1])dp = copy.deepcopy(matrix)# 初始化for i in range(1,m):dp[i][0] = dp[i-1][0]+matrix[i][0]for j in range(1,n):dp[0][j] = dp[0][j-1]+matrix[0][j]for i in range(1,m):for j in range(1,n):dp[i][j] = matrix[i][j] + min(dp[i-1][j],dp[i][j-1])return dp[-1][-1]