LeetCode 63: Unique Paths II ·

基本資料
#

難易度: medium 第一次嘗試：2026-06-27 來源：Day 29 learning note

學習脈絡
#

這篇是從 learning note 裡該 LeetCode 題目的段落重新整理出來的版本。我保留當天筆記中的修正點、比較點、容易犯錯的地方，並移除同一天其他非 LeetCode 主題，避免文章內容混題。

筆記中提到的相關提醒
#

LC 63: pass after boundary pushback

當天筆記摘錄
#

Problem 2 - LC 63 Unique Paths II
#

Pattern: 2D counting DP with blocked cells.

Why This Fits
#

This is the same table as LC 62, with one upgrade:

some cells are unreachable because they are obstacles

So the real test is not a new pattern.

It is whether you can preserve the old state meaning under a new legality rule.

Core State / Invariant
#

dp[r][c] = number of valid paths from the start to cell (r, c) without stepping on obstacles

Base Cases
#

If the start cell is blocked:

answer = 0

Otherwise:

dp[0][0] = 1

Boundary nuance:

first row cells stay reachable only until the first obstacle appears
first column cells stay reachable only until the first obstacle appears

Because after an obstacle on the boundary:

there is no alternative route from above or left on that boundary

Transition
#

If the current cell is an obstacle:

dp[r][c] = 0

Otherwise:

dp[r][c] = dp[r - 1][c] + dp[r][c - 1]

Complexity
#

Time: O(m * n)
Space: O(m * n)

Can also be compressed to:

Space: O(n)

Common Mistakes
#

forgetting that blocked start cell means immediate 0
filling the first row / first column with 1 even after an obstacle already appeared
using the LC 62 recurrence blindly without zeroing obstacle cells
saying the obstacle cell is -inf or None instead of 0 ways

Strong Spoken Explanation
#

I keep the same state as LC 62: dp[r][c] is the number of valid paths to cell (r, c). The difference is that obstacle cells contribute zero paths because I am not allowed to stand on them. If the start is blocked, the answer is immediately zero. For non-obstacle cells, the recurrence is still up + left, but the boundary initialization must stop once an obstacle appears because cells later on that boundary are no longer reachable from only one direction.

正確解法
#

上面的筆記保留了推理脈絡和當天需要修正的點。下面是我會提交的版本。

from typing import List

class Solution:
    def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
        m, n = len(obstacleGrid), len(obstacleGrid[0])
        dp = [0] * n
        dp[0] = 1

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

        return dp[-1]