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]