力扣63. 不同路径 II（动态规划）
大致思路与 力扣63. 不同路径 的方法一致。不过赋值前都要看obstacleGrid数组有无障碍，有障碍直接为0，无障碍则按照力扣63. 不同路径 I的方法
// // main.cpp // 63uniquePathsWithObstacles // // Created by MXQ on 2020/10/21. // #include <iostream> #include<vector> using namespace std; class Solution { public: int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) { if (obstacleGrid.size()==0) { return 0; } if (obstacleGrid.size()==1 && obstacleGrid[0].size()==0) { return 1; } if (obstacleGrid.size()!=1 && obstacleGrid[0].size()==0) { return 0; } int m=obstacleGrid.size(); int n=obstacleGrid[0].size(); vector<vector<int>>f(m,vector<int>(n)); //动态规划数组赋值前都要看obstacleGrid数组有无障碍，有障碍直接为0，无障碍则按照力扣63. 不同路径 I的方法 f[0][0]=obstacleGrid[0][0]==1?0:1; for (int i=1; i<m; i++) { if (obstacleGrid[i][0]==1) { f[i][0]=0; continue; } f[i][0]=f[i-1][0]; } for (int j=1; j<n; j++) { if (obstacleGrid[0][j]==1) { f[0][j]=0; continue; } f[0][j]=f[0][j-1]; } for (int i=1; i<m; i++) { for (int j=1; j<n; j++) { if (obstacleGrid[i][j]==1) { f[i][j]=0; continue; } else{ f[i][j]=f[i-1][j]+f[i][j-1]; } } } return f[m-1][n-1]; } }; int main(int argc, const char * argv[]) { // insert code here... Solution s; vector<vector<int>> obstacleGrid(3,vector<int>(3)); obstacleGrid[1][1]=1; auto result=s.uniquePathsWithObstacles(obstacleGrid); std::cout << result<<endl; std::cout << "Hello, World!\n"; return 0; }
