63. 不同路径 IIhttps://leetcode.cn/problems/unique-paths-ii/

输入：obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
输出：2
解释：3x3 网格的正中间有一个障碍物。
从左上角到右下角一共有 2 条不同的路径：
1. 向右 -> 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右 -> 向右

 

与dp6思路相同，只需要增加条件判断即可。

class Solution {
public:int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {int m=obstacleGrid.size(),n=obstacleGrid[0].size();vector<vector<int>> dp(m+1,vector<int>(n+1));dp[0][1]=1;for(int i=1;i<=m;i++){for(int j=1;j<=n;j++){if(obstacleGrid[i-1][j-1]!=1)dp[i][j]=dp[i][j-1]+dp[i-1][j];}}return dp[m][n];}
};