数据结构
网络
关系数据库管理系统 (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 次浏览
广告