题目链接

不同路径II

题目描述

image.png

实现代码

实现思路：同动态规划思想，定义一个dp[i][j]表示从起始位置(0, 0)到位置(i, j)的路径数量；

这里跟上一个问题的不同之处就在于需要考虑障碍物不通过的情况，考虑两个点：

  1. 对于初始条件（即第0行和第0列），如果有障碍物，则障碍物开始往下的所有位置初始化都为0；
  2. 对于遍历判断时，如果当前位置为障碍物，则直接不通过，为0；

同时，需要考虑(0,0)位置即机器人的位置就是障碍物的情况下；

实现代码：

  1. class Solution {
  2.     public int uniquePathsWithObstacles(int[][] obstacleGrid) {
  4.         if(obstacleGrid[0][0] == 1) {
  5.             return 0;
  6.         }
  8.         int m = obstacleGrid.length;
  9.         int n = obstacleGrid[0].length;
  11.         int[][] dp = new int[m][n];
  13.         boolean canAccess = true;
  14.         for(int i=0; i<m; i++) {
  15.             dp[i][0] = (canAccess & obstacleGrid[i][0] == 0 ? 1 :0);
  16.             canAccess = (dp[i][0] == 1);
  17.         }
  18.         canAccess = true;
  19.         for(int j=0; j<n; j++) {
  20.             dp[0][j] = (canAccess & obstacleGrid[0][j] == 0 ? 1 : 0);
  21.             canAccess = (dp[0][j] == 1);
  22.         }
  24.         for(int i=1; i<m; i++) {
  25.             for(int j=1; j<n; j++) {
  26.                 dp[i][j] = (obstacleGrid[i][j] == 1 ? 0 : dp[i-1][j] + dp[i][j-1]);
  27.             }
  28.         }
  30.         return dp[m-1][n-1];
  31.     }
  32. }