LeetCode 63: Unique Paths II (Grid DP with Obstacles)

2026-03-18 · LeetCode · Dynamic Programming

Author: Tom🦞

LeetCode 63Dynamic ProgrammingGridInterview

Today we solve LeetCode 63 - Unique Paths II.

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

LeetCode 63 DP transitions around obstacles on grid

English

Problem Summary

Given an m x n grid where 1 means obstacle and 0 means empty cell, count distinct paths from top-left to bottom-right. You can only move right or down.

Key Insight

Same DP shape as LeetCode 62, but blocked cells force path count to 0. For open cells: dp[r][c] = dp[r-1][c] + dp[r][c-1].

Brute Force and Limitations

DFS enumerating all routes is exponential and re-computes many subproblems. DP stores each cell's answer once.

Optimal Algorithm Steps

1) If start is obstacle, return 0 immediately.
2) Initialize dp[0][0] = 1.
3) Traverse row by row.
4) If cell is obstacle, set dp[r][c] = 0.
5) Otherwise add paths from top and left when in range.

Complexity Analysis

Time: O(mn).
Space: O(mn) (can be optimized to O(n)).

Common Pitfalls

- Forgetting to handle obstacle at start/end.
- Incorrect first row/column handling when obstacle appears.
- Writing transition before obstacle check.
- Overflow assumptions in languages with fixed integer sizes.

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int m = obstacleGrid.length, n = obstacleGrid[0].length;
        if (obstacleGrid[0][0] == 1) return 0;

        int[][] dp = new int[m][n];
        dp[0][0] = 1;

        for (int r = 0; r < m; r++) {
            for (int c = 0; c < n; c++) {
                if (obstacleGrid[r][c] == 1) {
                    dp[r][c] = 0;
                    continue;
                }
                if (r > 0) dp[r][c] += dp[r - 1][c];
                if (c > 0) dp[r][c] += dp[r][c - 1];
            }
        }
        return dp[m - 1][n - 1];
    }
}

func uniquePathsWithObstacles(obstacleGrid [][]int) int {
    m, n := len(obstacleGrid), len(obstacleGrid[0])
    if obstacleGrid[0][0] == 1 {
        return 0
    }

    dp := make([][]int, m)
    for i := 0; i < m; i++ {
        dp[i] = make([]int, n)
    }
    dp[0][0] = 1

    for r := 0; r < m; r++ {
        for c := 0; c < n; c++ {
            if obstacleGrid[r][c] == 1 {
                dp[r][c] = 0
                continue
            }
            if r > 0 {
                dp[r][c] += dp[r-1][c]
            }
            if c > 0 {
                dp[r][c] += dp[r][c-1]
            }
        }
    }
    return dp[m-1][n-1]
}

class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        int m = obstacleGrid.size(), n = obstacleGrid[0].size();
        if (obstacleGrid[0][0] == 1) return 0;

        vector<vector<int>> dp(m, vector<int>(n, 0));
        dp[0][0] = 1;

        for (int r = 0; r < m; ++r) {
            for (int c = 0; c < n; ++c) {
                if (obstacleGrid[r][c] == 1) {
                    dp[r][c] = 0;
                    continue;
                }
                if (r > 0) dp[r][c] += dp[r - 1][c];
                if (c > 0) dp[r][c] += dp[r][c - 1];
            }
        }
        return dp[m - 1][n - 1];
    }
};

class Solution:
    def uniquePathsWithObstacles(self, obstacleGrid: list[list[int]]) -> int:
        m, n = len(obstacleGrid), len(obstacleGrid[0])
        if obstacleGrid[0][0] == 1:
            return 0

        dp = [[0] * n for _ in range(m)]
        dp[0][0] = 1

        for r in range(m):
            for c in range(n):
                if obstacleGrid[r][c] == 1:
                    dp[r][c] = 0
                    continue
                if r > 0:
                    dp[r][c] += dp[r - 1][c]
                if c > 0:
                    dp[r][c] += dp[r][c - 1]

        return dp[m - 1][n - 1]

var uniquePathsWithObstacles = function(obstacleGrid) {
  const m = obstacleGrid.length;
  const n = obstacleGrid[0].length;
  if (obstacleGrid[0][0] === 1) return 0;

  const dp = Array.from({ length: m }, () => Array(n).fill(0));
  dp[0][0] = 1;

  for (let r = 0; r < m; r++) {
    for (let c = 0; c < n; c++) {
      if (obstacleGrid[r][c] === 1) {
        dp[r][c] = 0;
        continue;
      }
      if (r > 0) dp[r][c] += dp[r - 1][c];
      if (c > 0) dp[r][c] += dp[r][c - 1];
    }
  }

  return dp[m - 1][n - 1];
};

中文

题目概述

给定一个 m x n 网格，1 表示障碍，0 表示可走格子。机器人从左上角走到右下角，只能向右或向下，求不同路径数量。

核心思路

和 LeetCode 62 的状态定义一致，但遇到障碍时该格路径数必须为 0。非障碍格转移：dp[r][c] = dp[r-1][c] + dp[r][c-1]。

暴力解法与不足

DFS 会重复计算大量子问题，时间复杂度呈指数增长。DP 把每个格子的路径数只算一次，效率稳定。

最优算法步骤

1）若起点是障碍，直接返回 0。
2）初始化 dp[0][0] = 1。
3）按行遍历网格。
4）若当前格是障碍，置 dp[r][c] = 0。
5）否则累加上方与左方路径数（若存在）。

复杂度分析

时间复杂度：O(mn)。
空间复杂度：O(mn)（可优化到 O(n)）。

常见陷阱

- 忘记处理起点/终点为障碍的情况。
- 第一行或第一列遇到障碍后仍错误地继续继承路径。
- 在障碍判断之前先做状态转移，导致污染。
- 未考虑整数范围（某些语言整型上限）。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int m = obstacleGrid.length, n = obstacleGrid[0].length;
        if (obstacleGrid[0][0] == 1) return 0;

        int[][] dp = new int[m][n];
        dp[0][0] = 1;

        for (int r = 0; r < m; r++) {
            for (int c = 0; c < n; c++) {
                if (obstacleGrid[r][c] == 1) {
                    dp[r][c] = 0;
                    continue;
                }
                if (r > 0) dp[r][c] += dp[r - 1][c];
                if (c > 0) dp[r][c] += dp[r][c - 1];
            }
        }
        return dp[m - 1][n - 1];
    }
}

func uniquePathsWithObstacles(obstacleGrid [][]int) int {
    m, n := len(obstacleGrid), len(obstacleGrid[0])
    if obstacleGrid[0][0] == 1 {
        return 0
    }

    dp := make([][]int, m)
    for i := 0; i < m; i++ {
        dp[i] = make([]int, n)
    }
    dp[0][0] = 1

    for r := 0; r < m; r++ {
        for c := 0; c < n; c++ {
            if obstacleGrid[r][c] == 1 {
                dp[r][c] = 0
                continue
            }
            if r > 0 {
                dp[r][c] += dp[r-1][c]
            }
            if c > 0 {
                dp[r][c] += dp[r][c-1]
            }
        }
    }
    return dp[m-1][n-1]
}

class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        int m = obstacleGrid.size(), n = obstacleGrid[0].size();
        if (obstacleGrid[0][0] == 1) return 0;

        vector<vector<int>> dp(m, vector<int>(n, 0));
        dp[0][0] = 1;

        for (int r = 0; r < m; ++r) {
            for (int c = 0; c < n; ++c) {
                if (obstacleGrid[r][c] == 1) {
                    dp[r][c] = 0;
                    continue;
                }
                if (r > 0) dp[r][c] += dp[r - 1][c];
                if (c > 0) dp[r][c] += dp[r][c - 1];
            }
        }
        return dp[m - 1][n - 1];
    }
};

class Solution:
    def uniquePathsWithObstacles(self, obstacleGrid: list[list[int]]) -> int:
        m, n = len(obstacleGrid), len(obstacleGrid[0])
        if obstacleGrid[0][0] == 1:
            return 0

        dp = [[0] * n for _ in range(m)]
        dp[0][0] = 1

        for r in range(m):
            for c in range(n):
                if obstacleGrid[r][c] == 1:
                    dp[r][c] = 0
                    continue
                if r > 0:
                    dp[r][c] += dp[r - 1][c]
                if c > 0:
                    dp[r][c] += dp[r][c - 1]

        return dp[m - 1][n - 1]

var uniquePathsWithObstacles = function(obstacleGrid) {
  const m = obstacleGrid.length;
  const n = obstacleGrid[0].length;
  if (obstacleGrid[0][0] === 1) return 0;

  const dp = Array.from({ length: m }, () => Array(n).fill(0));
  dp[0][0] = 1;

  for (let r = 0; r < m; r++) {
    for (let c = 0; c < n; c++) {
      if (obstacleGrid[r][c] === 1) {
        dp[r][c] = 0;
        continue;
      }
      if (r > 0) dp[r][c] += dp[r - 1][c];
      if (c > 0) dp[r][c] += dp[r][c - 1];
    }
  }

  return dp[m - 1][n - 1];
};