C ++中的独特路径II

假设有一个机器人位于anxm网格的左上角（n行m列）。机器人在任何时间点只能向下或向右移动。机器人希望到达网格的右下角（在下图中标记为“ END”）。

网格中的某些单元被标记，这将被视为障碍。因此，我们必须找到多少个可能的唯一路径？例如，如果网格类似于[[0,0,0]，[0,1,0]，[0,0,0]]，则网格将类似于下面的−

输出将为2，因此从起始位置到结束位置共有2种不同的到达方式。这些路径是-

1. 右→右→下→下

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