不同路径-有障碍

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。
现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/unique-paths-ii
注：题目的数组中有障碍为1，没有障碍为0
image.png
思路：
首先边界值的问题，第一行和第一列只能为1，因为只有一条路可以走
边界：dp[i][0] = 1;dp[0][i] = 1;
如果有障碍那么在这个障碍以后的都不可达

  1.  // 第一行只能往右走为1，遇到障碍物后面都为0
  2. for(int i = 0;i<n&&obstacleGrid[0][i]==0;i++){
  3.     dp[0][i] = 1;  //第一行能够通行的为1;
  4. }
  5. // 第一列
  6. for(int i = 0;i<m&&obstacleGrid[i][0]==0;i++){
  7.     dp[i][0] = 1;
  8. }
  1.  中间路径：然后从小扩展到大来看，每一个位置只能从它的上面或者他的左边来。<br />![image.png](https://cdn.nlark.com/yuque/0/2021/png/2875045/1628753372003-669fe0c9-07cf-46f1-b2d5-97f47909e9cf.png#clientId=u2c027fe5-4c04-4&from=paste&height=88&id=u9e75e57e&margin=%5Bobject%20Object%5D&name=image.png&originHeight=175&originWidth=262&originalType=binary&ratio=1&size=7987&status=done&style=none&taskId=uf6564573-56d5-4aa6-9d9d-e25affc1276&width=131)从左上角到右下角，也就是dp[i-1][j]+dp[i][j-1]的组合。<br />![image.png](https://cdn.nlark.com/yuque/0/2021/png/2875045/1628753835529-474624d6-1e4a-4942-b450-72a085aaf1c5.png#clientId=u2c027fe5-4c04-4&from=paste&height=196&id=uf4fb4815&margin=%5Bobject%20Object%5D&name=image.png&originHeight=391&originWidth=418&originalType=binary&ratio=1&size=26887&status=done&style=none&taskId=uc1e81151-b982-4048-944b-ab087ccb3e8&width=209)扩大一点可以看出确实是这个意思。<br />![image.png](https://cdn.nlark.com/yuque/0/2021/png/2875045/1628754117704-f93d155f-0178-485e-8ab9-48f8af06619a.png#clientId=u2c027fe5-4c04-4&from=paste&height=162&id=u7df83e0e&margin=%5Bobject%20Object%5D&name=image.png&originHeight=323&originWidth=398&originalType=binary&ratio=1&size=22112&status=done&style=none&taskId=u9ff2c7be-37fe-47b8-9f3d-e81f699f9d2&width=199) 有障碍表示此路不通，也不可达直接为0，也就是不改变值。
  1. for(int i = 1;i<m;i++){
  2.     for(int j  =1;j<n;j++){
  3.         if(obstacleGrid[i][j]==0){
  4.             // 等于0表示可以通行
  5.             dp[i][j] = dp[i-1][j]+dp[i][j-1];
  6.         }
  7.     }
  8. }

代码

  1. class Solution {
  2.     // 遇到障碍为0
  3.     public int uniquePathsWithObstacles(int[][] obstacleGrid) {
  4.         if(obstacleGrid.length == 0) return 0;
  5.         int m = obstacleGrid.length,n = obstacleGrid[0].length;
  6.         int[][] dp = new int[m][n];
  7.         // 第一行只能往右走为1，遇到障碍物后面都为0
  8.         for(int i = 0;i<n&&obstacleGrid[0][i]==0;i++){
  9.             dp[0][i] = 1;  //第一行能够通行的为1;
  10.         }
  11.         // 第一列
  12.         for(int i = 0;i<m&&obstacleGrid[i][0]==0;i++){
  13.             dp[i][0] = 1;
  14.         }
  15.         for(int i = 1;i<m;i++){
  16.             for(int j  =1;j<n;j++){
  17.                 if(obstacleGrid[i][j]==0){
  18.                     // 等于0表示可以通行
  19.                     dp[i][j] = dp[i-1][j]+dp[i][j-1];
  20.                 }
  21.             }
  22.         }
  23.         return dp[m-1][n-1];
  24.     }
  25. }