一個機器人位于一個 m x n 網(wǎng)格的左上角 （起始點在下圖中標記為 “Start” ）。

機器人每次只能向下或者向右移動一步。機器人試圖達到網(wǎng)格的右下角（在下圖中標記為 “Finish”）。

現(xiàn)在考慮網(wǎng)格中有障礙物。那么從左上角到右下角將會有多少條不同的路徑？

網(wǎng)格中的障礙物和空位置分別用 1 和 0 來表示。

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/unique-paths-ii
?

例：

輸入：obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
輸出：2
解釋：3x3 網(wǎng)格的正中間有一個障礙物。
從左上角到右下角一共有 2 條不同的路徑：
1. 向右 -> 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右 -> 向右

解析：和最基本的不同路徑一樣，只是多了一個障礙物，在設(shè)置dp數(shù)組時將有障礙物的地方設(shè)置為0即可。

class Solution(object):def uniquePathsWithObstacles(self, obstacleGrid):""":type obstacleGrid: List[List[int]]:rtype: int"""m, n = len(obstacleGrid), len(obstacleGrid[0]) # dp數(shù)組的行列dp = [[0 for _ in range(n)] for _ in range(m)] # dp數(shù)組初始化i, j = 0, 0while i < m and obstacleGrid[i][0] == 0: # 最左邊一條，若有障礙物則置為0dp[i][0] = 1i += 1while j < n and obstacleGrid[0][j] == 0: # 最上面一條，若有障礙物置為0dp[0][j] = 1j += 1for i in range(1, m): # dp數(shù)組for j in range(1, n):if obstacleGrid[i][j] == 1: # 跳過障礙物continuedp[i][j] = dp[i - 1][j] + dp[i][j - 1] # 關(guān)鍵語句return dp[m - 1][n - 1] # 返回最后一格

總結(jié)

以上是生活随笔為你收集整理的不同路径 IIPython解法的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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