Title

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

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

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

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

說明：m 和 n 的值均不超過 100。

示例 1:

輸入:
[
[0,0,0],
[0,1,0],
[0,0,0]
]
輸出: 2

解釋:

3x3 網格的正中間有一個障礙物。
從左上角到右下角一共有 2 條不同的路徑：

向右 -> 向右 -> 向下 -> 向下

向下 -> 向下 -> 向右 -> 向右

動態規劃

如果我們熟悉這類問題，可以一眼看出這是一個動態規劃問題。當我們不熟悉的時候，怎么想到用動態規劃來解決這個問題呢？我們需要從問題本身出發，尋找一些有用的信息，例如本題中：

• (i,j) 位置只能從 (i - 1, j) 和 (i, j - 1) 走到，這樣的條件就是在告訴我們這里轉移是 「無后效性」 的，f(i, j) 和任何的 f(i’, j’)(i’ > i, j’ > j) 無關。
• 動態規劃的題目分為兩大類，一種是求最優解類，典型問題是背包問題，另一種就是計數類，比如這里的統計方案數的問題，它們都存在一定的遞推性質。前者的遞推性質還有一個名字，叫做 「最優子結構」 ——即當前問題的最優解取決于子問題的最優解，后者類似，當前問題的方案數取決于子問題的方案數。所以在遇到求方案數的問題時，我們可以往動態規劃的方向考慮。

通常如果我們察覺到了這兩點要素，這個問題八成可以用動態規劃來解決。

Solve

我們用 f(i, j) 來表示從坐標 (0, 0) 到坐標 (i, j) 的路徑總數，u(i, j) 表示坐標 (i, j) 是否可行，如果坐標 (i, j) 有障礙物，u(i, j) = 0，否則 u(i, j) = 1。

因為「機器人每次只能向下或者向右移動一步」，所以從坐標 (0, 0) 到坐標 (i, j) 的路徑總數的值只取決于從坐標 (0, 0) 到坐標 (i - 1, j) 的路徑總數和從坐標 (0, 0) 到坐標 (i, j - 1) 的路徑總數，即 f(i, j) 只能通過 f(i - 1, j) 和 f(i, j - 1) 轉移得到。

當坐標 (i, j) 本身有障礙的時候，任何路徑都到到不了 f(i, j)，此時 f(i, j) = 0；下面我們來討論坐標 (i, j) 沒有障礙的情況：如果坐標 (i - 1, j) 沒有障礙，那么就意味著從坐標 (i - 1, j) 可以走到 (i, j)，即 (i - 1, j) 位置對 f(i, j) 的貢獻為 f(i - 1, j)，同理，當坐標 (i, j - 1) 沒有障礙的時候，(i, j - 1) 位置對 f(i, j) 的貢獻為 f(i, j - 1)。

綜上所述，我們可以得到這樣的動態規劃轉移方程：

$$dp[i][j]=\{\begin{array}{ll}0,& u(i,j)=0\\ f(i?1,j)+f(i,j?1),& u(i,j)!=0\end{array}$$

很顯然我們可以給出一個時間復雜度 O(nm) 并且空間復雜度也是 O(nm) 的實現，由于這里 f(i, j) 只與 f(i - 1, j) 和 f(i, j - 1) 相關，我們可以運用「滾動數組思想」把空間復雜度優化稱 O(m)。

Code

def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:rows, cols = len(obstacleGrid), len(obstacleGrid[0])dp = [1] + [0] * colsfor i in range(0, rows):for j in range(0, cols):dp[j] = 0 if obstacleGrid[i][j] else dp[j] + dp[j - 1]return dp[-2]

復雜度分析

時間復雜度：O(nm)，其中 n 為網格的行數，m 為網格的列數。我們只需要遍歷所有網格一次即可。
空間復雜度：O(m)。利用滾動數組優化，我們可以只用 O(m)O(m) 大小的空間來記錄當前行的 ff 值。

與50位技術專家面對面20年技術見證，附贈技術全景圖

總結

以上是生活随笔為你收集整理的63. Unique Paths II 不同路径 II的全部內容，希望文章能夠幫你解決所遇到的問題。

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