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 傳遞為網格的表示，以獲得不同不含障礙物的獨特路徑數。