步驟一、確定狀態(tài):

1、確定原問題中變化的變量個數(shù) 2、考慮最后一步
右下角坐標設為(m-1,n-1) 那么前一步一定是在(m-2,n-1)或者(m-1,n-2)

步驟二、推斷狀態(tài)方程:

f[i][j] =從(0,0)走到(i,j)的路徑最小數(shù)字總和

步驟二、推斷狀態(tài)方程:

f[i][j] =從(0,0)走到(i,j)的路徑最小數(shù)字總和 A[i][j] 格子(i,j)的數(shù)字
f[i][j] = min{f[i-i][j],f[i][j-1]}+A[i][j]

步驟三、規(guī)定初始條件和邊界:

初始條件:
f[0][0]=A[0][0] 邊界情況:i=0或j=0，前一步只有一個方向能過來

步驟四、計算順序:

自底向上
先計算第0行，f[0][0] ....f[0][n-1] 計算第1行: f[1][0] ....f[1][n-1]
...
計算第m-1行: f[m-1][0] ....f[m-1][n-1]

class Solution:def minPathSum(self, grid: List[List[int]]) -> int:if not grid:return m, n = len(grid), len(grid[0])dp = [[0 for _ in range(n)] for _ in range(m)]dp[0][0] = grid[0][0]for i in range(1, m):dp[i][0] = dp[i-1][0] + grid[i][0]for j in range(1, n):dp[0][j] = dp[0][j-1] + grid[0][j]for i in range(1, m):for j in range(1, n):dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]return dp[-1][-1]

?

總結

以上是生活随笔為你收集整理的93. Leetcode 64. 最小路径和 (动态规划-路径规划)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內容還不錯，歡迎將生活随笔推薦給好友。