C ++中的独特路径II
假设有一个机器人位于anxm网格的左上角（n行m列）。机器人在任何时间点只能向下或向右移动。机器人希望到达网格的右下角（在下图中标记为“END”）。
网格中的某些单元被标记，这将被视为障碍。因此，我们必须找到多少个可能的唯一路径？例如，如果网格类似于[[0,0,0]，[0,1,0]，[0,0,0]]，则网格将类似于下面的−
输出将为2，因此从起始位置到结束位置共有2种不同的到达方式。这些路径是-
右→右→下→下
向下→向下→右→右
让我们看看步骤-
a：=行数，b：=列数
如果grid[a–1，b-1]不为零，则返回0
创建一个表，其顺序为axb，名称为DP
对于i：=b–1降至0
如果grid[a–1，i]，则中断，否则DP[a–1，i]：=1
对于我：=a–1降至0
如果grid[i，b-1]，则中断，否则DP[i，b–1]：=1
对于我：=a–2降至0
DP[i，j]：=当DP[i，j]为0时为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