1.题目
![](https://img.laitimes.com/img/_0nNw4CM6IyYiwiM6ICdiwiI0gTMx81dsQWZ4lmZf1GLlpXazVmcvwFciV2dsQXYtJ3bm9CX9s2RkBnVHFmb1clWvB3MaVnRtp1XlBXe0xCMy81dvRWYoNHLwEzX5xCMx8FesU2cfdGLwMzX0xiRGZkRGZ0Xy9GbvNGLpZTY1EmMZVDUSFTU4VFRR9Fd4VGdsYTMfVmepNHLrJXYtJXZ0F2dvwVZnFWbp1zczV2YvJHctM3cv1Ce-cmbw5CO4MjN5MmNyEmNwETY3Y2YyYzX4AjNwATM0EzLcdDMyIDMy8CXn9Gbi9CXzV2Zh1WavwVbvNmLvR3YxUjLyM3Lc9CX6MHc0RHaiojIsJye.png)
2.思路
(1)确定状态
表示从到右下角(终点)的最短路径
(2)转移方程
(3)初始条件+边界条件
dp[0][0] = grid[0][0]
注意:
3.代码
class Solution:
def minPathSum(self, grid: List[List[int]]) -> int:
m = len(grid) # 行数
n = len(grid[0]) # 列数
dp = [[0] * n for k in range(m)]
dp[0][0] = grid[0][0]
for i in range(m):
for j in range(n):
if i == 0 and j!= 0:# 第一行
dp[i][j] = grid[i][j] + dp[i][j - 1]
elif i != 0 and j == 0: # 第一列
dp[i][j] = grid[i][j] + dp[i - 1][j]
elif i != 0 and j != 0:
dp[i][j] = grid[i][j] + min(dp[i - 1][j], dp[i][j - 1])
return dp[m - 1][n - 1]