一、题目

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。

现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？
63. 不同路径 II - 图1

网格中的障碍物和空位置分别用 1 和 0 来表示。

点击查看原题

二、思路

动态规划：
跟题目不同路径很相似，动态规划的解法，设定有一数组dp，dp[i][j]表示可以到达(i, j)格子的路径数量，可以得到状态转移方程：
63. 不同路径 II - 图2
而不一样的是需要考虑到障碍物的情况，有障碍物的网格处于不可达状态，也就是当obstacleGrid[i][j]==0时，dp[i][j]=0.
空间压缩到一维：
由于状态(i, j)状态只依赖于上一行和前一列，所以可以将dp数组降为二维：
63. 不同路径 II - 图3
同样的，当obstacleGrid[i][j]==0时，dp[j]=0.

三、代码

动态规划

  1. class Solution {
  2.     public int uniquePathsWithObstacles(int[][] obstacleGrid) {
  3.         int[][] dp = new int[obstacleGrid.length][obstacleGrid[0].length];
  4.         dp[0][0] = obstacleGrid[0][0] == 1? 0 : 1;;
  5.         for (int i = 1; i < dp[0].length; i++) {    // 初始化第一行
  6.             if (obstacleGrid[0][i] == 1) {
  7.                 dp[0][i] = 0;
  8.             } else {
  9.                 dp[0][i] = dp[0][i-1];    // 如果出现过障碍物，则可达为0
  10.             }
  11.         }
  12.         for (int row = 1; row < dp.length; row++) {
  13.             for (int col = 0; col < dp[0].length; col++) {
  14.                 if (obstacleGrid[row][col] == 1) {    // 障碍物处不可达
  15.                     dp[row][col] = 0;
  16.                     continue;
  17.                 }
  18.                 if (col == 0) {
  19.                     dp[row][col] = dp[row-1][col];    // 考虑第0列的情况
  20.                 } else {
  21.                     dp[row][col] = dp[row-1][col] + dp[row][col-1];    // 状态转移
  22.                 }
  23.             }
  24.         }
  25.         return dp[dp.length - 1][dp[0].length - 1];
  26.     }
  27. }

时间复杂度为O(rowcol)，空间复杂度为O(rowcol).

空间压缩到一维：

  1. class Solution {
  2.     public int uniquePathsWithObstacles(int[][] obstacleGrid) {
  3.         int[] dp = new int[obstacleGrid[0].length];
  4.         dp[0] = obstacleGrid[0][0] == 1? 0 : 1;;
  5.         for (int i = 1; i < dp.length; i++) {
  6.             if (obstacleGrid[0][i] == 1) {
  7.                 dp[i] = 0;
  8.             } else {
  9.                 dp[i] = dp[i-1];
  10.             }
  11.         }
  12.         for (int row = 1; row < obstacleGrid.length; row++) {
  13.             for (int col = 0; col < obstacleGrid[0].length; col++) {
  14.                 if (obstacleGrid[row][col] == 1) {
  15.                     dp[col] = 0;
  16.                     continue;
  17.                 }
  18.                 if (col == 0) {
  19.                     dp[col] = dp[col];
  20.                 } else {
  21.                     dp[col] = dp[col] + dp[col-1];
  22.                 }
  23.             }
  24.         }
  25.         return dp[dp.length - 1];
  26.     }
  27. }

时间复杂度为O(row*col)，空间复杂度为O(col).