【題目】

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

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

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

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

示例 1：

示例 1.png

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

示例 2：

示例 2.png

輸入： obstacleGrid = [[0,1],[0,0]]
輸出： 1

提示：

• m == obstacleGrid.length
• n == obstacleGrid[i].length
• 1 <= m, n <= 100
• obstacleGrid[i][j] 為 0 或 1

【題目解析】

解題方法

這個問題是典型的動態(tài)規(guī)劃問題，其核心思想在于如何處理網(wǎng)格中的障礙物。我們創(chuàng)建一個與原網(wǎng)格大小相同的動態(tài)規(guī)劃表dp，其中dp[i][j]表示到達[i,j]位置的路徑數(shù)。關(guān)鍵步驟如下：

1. 初始化：初始化dp數(shù)組的第一行和第一列。如果遇到障礙物（即obstacleGrid[i][j] == 1），則該位置及其后面的位置均不可達，dp值為0。
2. 狀態(tài)轉(zhuǎn)移：對于dp表中的每一個位置，如果該位置有障礙物，則到達該位置的路徑數(shù)為0；如果沒有障礙物，則當(dāng)前位置的路徑數(shù)等于其上方和左方兩個位置的dp值之和。
3. 返回結(jié)果：最后，dp[m-1][n-1]即為到達網(wǎng)格右下角的路徑總數(shù)。

class Solution:
    def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
        if not obstacleGrid or not obstacleGrid[0]:
            return 0
        m, n = len(obstacleGrid), len(obstacleGrid[0])
        dp = [[0] * n for _ in range(m)]
        
        # 初始化第一列
        for i in range(m):
            if obstacleGrid[i][0] == 1:
                break
            dp[i][0] = 1
            
        # 初始化第一行
        for j in range(n):
            if obstacleGrid[0][j] == 1:
                break
            dp[0][j] = 1
        
        # 填充dp表
        for i in range(1, m):
            for j in range(1, n):
                if obstacleGrid[i][j] == 1:
                    dp[i][j] = 0
                else:
                    dp[i][j] = dp[i-1][j] + dp[i][j-1]
        
        return dp[m-1][n-1]

執(zhí)行效率

image.png

【總結(jié)】

適用問題類型

• 問題類別：動態(tài)規(guī)劃適用于多種問題類型，特別是可分解為重疊子問題的情況。"不同路徑 II"問題，考慮網(wǎng)格中障礙物的存在，是動態(tài)規(guī)劃在計數(shù)問題中的一種應(yīng)用。
• 示例問題："不同路徑 II"挑戰(zhàn)在于計算從網(wǎng)格左上角到右下角，繞過障礙物的所有可能路徑數(shù)量。

解決算法：動態(tài)規(guī)劃

• 算法核心：動態(tài)規(guī)劃算法通過構(gòu)建DP表（一般是二維數(shù)組）保存解決過的子問題的解，避免重復(fù)計算。該方法清晰定義了狀態(tài)、狀態(tài)轉(zhuǎn)移方程、初始狀態(tài)和邊界條件，為問題提供系統(tǒng)化解決框架。
• 系統(tǒng)框架：動態(tài)規(guī)劃為解決包含障礙物的路徑問題提供了一種系統(tǒng)化求解方法，通過逐步構(gòu)建解空間來達到最終解。

時間復(fù)雜度與空間復(fù)雜度

• 時間復(fù)雜度：O(m*n)，其中m和n分別代表網(wǎng)格的行和列數(shù)。這是因為算法需要遍歷整個網(wǎng)格來為每個單元格計算到達它的路徑數(shù)。
• 空間復(fù)雜度：O(m*n)，主要空間開銷來源于存儲每個單元格到達路徑數(shù)的DP表。通過狀態(tài)壓縮，可以在特定條件下將空間復(fù)雜度降至O(n)或O(m)。

實踐意義

• 廣泛應(yīng)用：動態(tài)規(guī)劃算法不僅適用于"不同路徑 II"這類路徑計數(shù)問題，還廣泛應(yīng)用于字符串處理、背包問題等多種復(fù)雜問題的解決，對提升編程和問題解決能力有顯著幫助。
• 優(yōu)化與應(yīng)用：通過優(yōu)化計算過程，動態(tài)規(guī)劃算法不僅提升了執(zhí)行效率，也增強了對復(fù)雜問題的處理能力，是算法學(xué)習(xí)和應(yīng)用中的關(guān)鍵技能之一。

總結(jié)而言，動態(tài)規(guī)劃方法對于解決"不同路徑 II"中考慮障礙物的路徑計數(shù)問題展現(xiàn)出了明顯優(yōu)勢，通過減少重復(fù)計算并系統(tǒng)地構(gòu)建解空間，顯著提高了問題解決的效率和可行性。

題目鏈接

不同路徑 II