题目地址(63. 不同路径 II)

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

题目描述

  1. 一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。
  3. 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。
  5. 现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？
  7. 网格中的障碍物和空位置分别用 1 和 0 来表示。
  11. 示例 1：
  13. 输入：obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
  14. 输出：2
  15. 解释：
  16. 3x3 网格的正中间有一个障碍物。
  17. 从左上角到右下角一共有 2 条不同的路径：
  18. 1. 向右 -> 向右 -> 向下 -> 向下
  19. 2. 向下 -> 向下 -> 向右 -> 向右
  22. 示例 2：
  24. 输入：obstacleGrid = [[0,1],[0,0]]
  25. 输出：1
  30. 提示：
  32. m == obstacleGrid.length
  33. n == obstacleGrid[i].length
  34. 1 <= m, n <= 100
  35. obstacleGrid[i][j] 为 0 或 1

前置知识


公司

  • 暂无

思路

这题和上题差不多 但是多了障碍物 如果有障碍物 obstacleGrid对应的坐标就是1 所以想法就是如果obstacleGrid[i][j]为1时 就将dp[i][j]设置为0

  1. 确定dp数组的含义
    跟上题一样 求的是到mn这个点的路径的条数
  2. 确定递推数组
    也是 dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
  3. 初始值
    第0行和第0列都是1 , 但是这里和上面不同的是有障碍物 我一开始的想法是如果有障碍物再把它设置为0 但是如果有障碍物了后面的也就都达不到了 所以如果0行和0列里有障碍物的话就将它之后的数据都跳过设置为1这个操作 后面的值也就都是默认的初始值0

image.png

//初始值
            for (int i = 0; i < m; i++) {
                if (obstacleGrid[i][0] == 1) {
                    break;
                }
                dp[i][0] = 1;
            }
            for (int i = 0; i < n; i++) {
                if (obstacleGrid[0][i] == 1) {
                    break;
                }
                dp[0][i] = 1;
            }
  1. 循环的方向
    和上题一样
  2. 举例推导
    自己画个图

image.png

关键点


代码

  • 语言支持：Java

Java Code:

class Solution {
        public int uniquePathsWithObstacles(int[][] obstacleGrid) {
            //行
            int m = obstacleGrid.length;
            //列
            int n = obstacleGrid[0].length;
            //dp
            int[][] dp = new int[m][n];
            //初始值
            for (int i = 0; i < m; i++) {
                if (obstacleGrid[i][0] == 1) {
                    break;
                }
                dp[i][0] = 1;
            }
            for (int i = 0; i < n; i++) {
                if (obstacleGrid[0][i] == 1) {
                    break;
                }
                dp[0][i] = 1;
            }
            for (int i = 1; i < m; i++) {
                for (int j = 1; j < n; j++) {
                    if (obstacleGrid[i][j] == 1) {
                        dp[i][j] = 0;
                        continue;
                    }
                    dp[i][j] = dp[i-1][j] + dp[i][j-1];
                }
            }
            return dp[m-1][n-1];
        }
    }

复杂度分析

令 n 为数组长度。

  • 时间复杂度：63. 不同路径 II - 图3#card=math&code=O%28n%29&id=aWYMl)
  • 空间复杂度：63. 不同路径 II - 图4#card=math&code=O%28n%29&id=HtYxT)