LeetCode Dynamic Programming_63.Unique Paths II(Medium)

 問題敘述如下:

這個問題是 "Unique Paths" 的變體,但現在網格中包含一些障礙物。給定一個包含障礙物和空格的 m x n 網格,請找出從左上角到右下角的不同不含障礙物的獨特路徑數量。

障礙物和空格分別用 1 和 0 來表示。


有多少種不同的獨特路徑可以達到終點?
注意:m 和 n 最大不超過 100。


[
  [0,0,0],
  [0,1,0],
  [0,0,0]
]
從左上角到右下角的不同不含障礙物的獨特路徑數為 2。



這個問題可以使用動態規劃(Dynamic Programming)解決,類似於 "Unique Paths" 問題。我們仍然使用一個二維數組 dp,其中 dp[i][j] 表示到達從左上角 (0, 0) 到 (i, j) 這個格子的不同獨特路徑數。但是,我們需要注意處理障礙物。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
class Solution {
public:
    int uniquePathsWithObstacles(std::vector<std::vector<int>>& obstacleGrid) {
        int m = obstacleGrid.size();
        int n = obstacleGrid[0].size();
        
        // 如果起點或終點有障礙物,則無法到達終點,返回 0。
        if (obstacleGrid[0][0] == 1 || obstacleGrid[m-1][n-1] == 1)
            return 0;
        
        // 創建大小為 (m x n) 的二維 DP 數組。
        std::vector<std::vector<int>> dp(m, std::vector<int>(n, 0));
        
        // 初始化左上角的格子為 1,因為到達它只有一種方法。
        dp[0][0] = 1;
        
        // 填充第一行和第一列,遇到障礙物則停止。
        for (int i = 1; i < m; ++i) {
            if (obstacleGrid[i][0] == 1)
                break;
            dp[i][0] = 1;
        }
        for (int j = 1; j < n; ++j) {
            if (obstacleGrid[0][j] == 1)
                break;
            dp[0][j] = 1;
        }
        
        // 使用自底向上的方法填充 DP 數組。
        for (int i = 1; i < m; ++i) {
            for (int j = 1; j < n; ++j) {
                if (obstacleGrid[i][j] == 0)
                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
                else
                    dp[i][j] = 0; // 如果有障礙物,設為 0。
            }
        }
        
        // 返回右下角的格子中的不同不含障礙物的獨特路徑數。
        return dp[m - 1][n - 1];
    }
};



當然,我可以幫助你解決 LeetCode 問題 "Unique Paths II"(問題#63),並提供一個 C++ 解決方案。

問題描述
這個問題是 "Unique Paths" 的變體,但現在網格中包含一些障礙物。給定一個包含障礙物和空格的 m x n 網格,請找出從左上角到右下角的不同不含障礙物的獨特路徑數量。

障礙物和空格分別用 1 和 0 來表示。

例如,給定以下網格:

csharp
Show diagram
Copy code
[
  [0,0,0],
  [0,1,0],
  [0,0,0]
]
從左上角到右下角的不同不含障礙物的獨特路徑數為 2。

解決方案
這個問題可以使用動態規劃(Dynamic Programming)解決,類似於 "Unique Paths" 問題。我們仍然使用一個二維數組 dp,其中 dp[i][j] 表示到達從左上角 (0, 0) 到 (i, j) 這個格子的不同獨特路徑數。但是,我們需要注意處理障礙物。

以下是用 C++ 編寫的解決方案:

cpp
Show diagram
Copy code
#include <vector>

class Solution {
public:
    int uniquePathsWithObstacles(std::vector<std::vector<int>>& obstacleGrid) {
        int m = obstacleGrid.size();
        int n = obstacleGrid[0].size();
        
        // 如果起點或終點有障礙物,則無法到達終點,返回 0。
        if (obstacleGrid[0][0] == 1 || obstacleGrid[m-1][n-1] == 1)
            return 0;
        
        // 創建大小為 (m x n) 的二維 DP 數組。
        std::vector<std::vector<int>> dp(m, std::vector<int>(n, 0));
        
        // 初始化左上角的格子為 1,因為到達它只有一種方法。
        dp[0][0] = 1;
        
        // 填充第一行和第一列,遇到障礙物則停止。
        for (int i = 1; i < m; ++i) {
            if (obstacleGrid[i][0] == 1)
                break;
            dp[i][0] = 1;
        }
        for (int j = 1; j < n; ++j) {
            if (obstacleGrid[0][j] == 1)
                break;
            dp[0][j] = 1;
        }
        
        // 使用自底向上的方法填充 DP 數組。
        for (int i = 1; i < m; ++i) {
            for (int j = 1; j < n; ++j) {
                if (obstacleGrid[i][j] == 0)
                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
                else
                    dp[i][j] = 0; // 如果有障礙物,設為 0。
            }
        }
        
        // 返回右下角的格子中的不同不含障礙物的獨特路徑數。
        return dp[m - 1][n - 1];
    }
};
解釋
我們首先確認左上角和右下角是否有障礙物。如果起點或終點有障礙物,則無法到達終點,直接返回 0。

創建一個大小為 m x n 的二維 DP 數組 dp,用於存儲每個格子的不同獨特路徑數。

初始化左上角的格子 dp[0][0] 為 1,因為機器人一開始就位於左上角(起點),所以只有一種方法可以達到該位置。

填充第一行和第一列的格子,遇到障礙物時停止填充,因為障礙物之後的格子都無法到達。

使用嵌套循環遍歷網格中的所有格子 (i, j)。如果格子 (i, j) 不是障礙物,则計算到達它的不同獨特路徑數,即 dp[i][j] = dp[i - 1][j] + dp[i][j - 1];如果是障礙物,則將 dp[i][j] 設為 0。

最後,dp[m-1][n-1] 中的值包含了到達右下角的不同不含障礙物的獨特路徑數,這就是我們的答案。

您可以將此函數呼叫並將 obstacleGrid 傳遞為網格的表示,以獲得不同不含障礙物的獨特路徑數。


留言

這個網誌中的熱門文章

何謂淨重(Net Weight)、皮重(Tare Weight)與毛重(Gross Weight)

Architecture(架構) 和 Framework(框架) 有何不同?_軟體設計前的事前規劃的藍圖概念

(2021年度)駕訓學科筆試準備題庫歸納分析_法規是非題