leetcode：63. 不同路径 II

题目

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish”）。
现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？
网格中的障碍物和空位置分别用 1 和 0 来表示。

示例 1：
[中等] 63. 不同路径 II - 图1

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

示例 2：
[中等] 63. 不同路径 II - 图2

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

解答 & 代码

二维动态规划：

  • 动态规划数组 dp：dp[i][j] 代表从起点 (0,0) 到 (i,j) 的不同路径数
  • 状态转移方程：[中等] 63. 不同路径 II - 图3
    • 因为每次只能往右或往下移动一步，因此到 (i,j) 的路径数等于到其上方 (i-1,j) 的路径数 + 到其左边 (i, j-1) 的路径数

  • 状态初始化：

    • dp[0][0] = grid[0][0] == 1 ? 0 : 1
    • 对于第一行，没有上方，只能取决于左边：dp[0][col] = grid[0][col] == 1 ? 0 : dp[0][col - 1]
    • 对于第一列，没有左边，只能取决于上方：dp[row][0] = grid[row][0] == 1 ? 0 : dp[row - 1][0]
      1. class Solution {
      2. public:
      3. int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
      4.    if(obstacleGrid.size() == 0 || obstacleGrid[0].size() == 0)
      5.        return 0;
      6.    int m = obstacleGrid.size();
      7.    int n = obstacleGrid[0].size();
      8.    // 动态规划数组 dp：dp[i][j] 代表从起点 (0,0) 到 (i,j) 的不同路径数
      9.    vector<vector<int>> dp(m, vector<int>(n, 0));
      10.    // 初始化
      11.    dp[0][0] = obstacleGrid[0][0] == 1 ? 0 : 1;
      12.    for(int col = 1; col < n; ++col)
      13.        dp[0][col] = obstacleGrid[0][col] == 1 ? 0 : dp[0][col - 1];
      14.    for(int row = 1; row < m; ++row)
      15.        dp[row][0] = obstacleGrid[row][0] == 1 ? 0 : dp[row - 1][0];
      16.    // 状态转移
      17.    for(int row = 1; row < m; ++row)
      18.    {
      19.        for(int col = 1; col < n; ++col)
      20.            dp[row][col] = obstacleGrid[row][col] ? 0 : dp[row - 1][col] + dp[row][col - 1];
      21.    }
      22.    return dp[m - 1][n - 1];
      23. }
      24. };
      复杂度分析：m*n 的网格

  • 时间复杂度 O(mn)：

  • 空间复杂度 O(mn)：

执行结果：

执行结果：通过

执行用时：4 ms, 在所有 C++ 提交中击败了 56.01% 的用户
内存消耗：7.6 MB, 在所有 C++ 提交中击败了 53.19% 的用户

优化为一维 dp 数组：滚动数组

class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        if(obstacleGrid.size() == 0 || obstacleGrid[0].size() == 0)
            return 0;
        int m = obstacleGrid.size();
        int n = obstacleGrid[0].size();
        vector<int> dp(n, 0);
        dp[0] = obstacleGrid[0][0] == 1 ? 0 : 1;
        for(int row = 0; row < m; ++row)
        {
            for(int col = 0; col < n; ++col)
            {
                if(obstacleGrid[row][col] == 1)
                    dp[col] = 0;
                else if(col - 1 >= 0)
                    dp[col] += dp[col - 1];
            }
        }
        return dp[n - 1];
    }
};

复杂度分析：m*n 的网格

  • 时间复杂度 O(mn)：
  • 空间复杂度 O(n)：

执行结果：

执行结果：通过

执行用时：4 ms, 在所有 C++ 提交中击败了 56.01% 的用户
内存消耗：7.5 MB, 在所有 C++ 提交中击败了 77.80% 的用户