难度

  • 简单
  • 中等
  • 困难

    标签

    动态规划

    题目描述

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

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

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

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

示例1：

63. 不同路径 II - 图2

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

实例2：

63. 不同路径 II - 图3

  1. 输入：obstacleGrid = [[0,1],[0,0]]
  2. 输出：1

题解

如果有障碍物，那么到该格的可能就为0。
因为只能往左或往下，所以第一行和第一列，如果有障碍物，则障碍物后面的可能也为0。

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