步驟一、確定狀態:

確定dp數組及含義 dp[i][j]表示從左上角到第i行j列這個位置的路徑條數

步驟二、推斷狀態方程

dp[i][j] = dp[i-1][j] + dp[i][j-1]

步驟三、規定初始條件:

初始條件:

dp = [[0 for _ in range(n)] for _ in range(m)]

步驟四、計算順序:

從(1,1)位置開始 i從1到m-1遍歷 j從1到n-1遍歷

class Solution:def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:m, n = len(obstacleGrid), len(obstacleGrid[0])dp = [[0 for _ in range(n)] for _ in range(m)]for i in range(m):if obstacleGrid[i][0] == 1:breakdp[i][0] = 1for j in range(n):if obstacleGrid[0][j] == 1:breakdp[0][j] = 1for i in range(1, m):for j in range(1, n):if obstacleGrid[i][j] == 1:continuedp[i][j] = dp[i-1][j] + dp[i][j-1]return dp[-1][-1]

總結

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

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