LeetCode 63. Unique Paths II

发表于 | 分类于 | 阅读量
字数统计: 563 | 阅读时长 ≈ 2

63.Unique Paths II（不同路径 II）

链接

https://leetcode-cn.com/problems/unique-paths-ii/

题目

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

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

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

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

说明： m 和 _n _的值均不超过 100。

示例 1:

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

思路

这题和上一题相似，区别在于存在阻碍无法通过，所以不能直接求公式，那么就采用dp算法，建立一个相同大小的数组，存放到达当前格子的路径数量。如果当前格子存在阻碍，那么就始终无法到达，设置为0，如果在第一行或者第一列，如果之前无阻碍就为1（只能通过直线到达），有阻碍就为0。中间的格子也是，有阻碍就为0，没阻碍就是上方格子和左侧格子的和，最后一个格子就是所需的路径数目。

本来我是把第一行第一列提出来先进行运算的，但是这样有点浪费时间，就把这些都放在一起了，好像快了一点点。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public int uniquePathsWithObstacles(int[][] obstacleGrid) {
    int m = obstacleGrid.length;
    int n = obstacleGrid[0].length;
    int[][] dp = new int[m][n];

    for (int i = 0; i < m; i++) {
      for (int j = 0; j < n; j++) {
        if (obstacleGrid[i][j] == 1) {
          dp[i][j] = 0;
        } else if (i == 0 && j == 0) {
          dp[i][j] = 1;
        } else if (i == 0 && j != 0) {
          dp[i][j] = dp[i][j - 1];
        } else if (j == 0 && i != 0) {
          dp[i][j] = dp[i - 1][j];
        } else {
          dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
        }
      }
    }
    return dp[m - 1][n - 1];
  }
---本文结束，感谢阅读---