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