資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學C++中的獨特路徑 II
假設有一個機器人位於n x m 網格（n行m列）的左上角。機器人只能在任何時間點向下或向右移動。機器人想要到達網格的右下角（下圖中標有“END”）。
網格中的一些單元格被標記為障礙物。因此，我們必須找到有多少條可能的獨特路徑？例如，如果網格類似於[[0,0,0],[0,1,0],[0,0,0]]，則網格將如下所示：
| 機器人 | ||
| 障礙物 | ||
| 終點 |
輸出將為2，因此共有2種不同的方法可以從起始位置到達終點位置。這些路徑是：
- 右 → 右 → 下 → 下
- 下 → 下 → 右 → 右
讓我們看看步驟：
- a := 行數，b := 列數
- 如果grid[a – 1,b - 1]非零，則返回0
- 建立一個大小為a x b的表，命名為DP
- 對於 i := b – 1 到 0
- 如果grid[a – 1, i]，則中斷，否則DP[a – 1, i] := 1
- 對於 i := a – 1 到 0
- 如果grid[i, b - 1]，則中斷，否則DP[i, b – 1] := 1
- 對於 i := a – 2 到 0
- 對於 j := b – 2 到 0
- 當grid[i, j]為0時，DP[i, j] := DP[i + 1, j] + DP[i, j + 1]，否則為0
- 對於 j := b – 2 到 0
- 返回DP[0, 0]
讓我們看看下面的實現，以便更好地理解：
示例
#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
class Solution {
public:
int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
int a = obstacleGrid.size();
int b = obstacleGrid[0].size();
if(!a || !b) return 0;
if(obstacleGrid[a - 1][b - 1])return 0;
vector < vector <lli> > dp(a, vector <lli>(b));
for(int i = b - 1; i >= 0; i--)if(obstacleGrid[a-1][i]) break; else dp[a-1][i] = 1;
for(int i = a - 1; i >= 0; i--)if(obstacleGrid[i][b - 1]) break; else dp[i][b-1] = 1 ;
for(int i = a-2; i >= 0; i--){
for(int j = b-2 ; j >= 0; j--)dp[i][j] = !obstacleGrid[i][j]? dp[i+1][j] + dp[i][j+1] : 0;
}
return dp[0][0];
}
};
main(){
Solution ob;
vector<vector<int>> v = {{0,0,0},{0,1,0},{0,0,0}};
cout << ob.uniquePathsWithObstacles(v);
}輸入
[[0,0,0],[0,1,0],[0,0,0]]
輸出
2
更新於：2020年5月4日
180 次瀏覽
廣告