Input: [[0,0,0],[0,1,0],[0,0,0]]
Output: 2
3×3グリッドで中央に障害物がある場合。2通りの経路が存在。
Input: [[0,1],[0,0]]
Output: 1
2×2グリッドで右上に障害物がある場合。1通りの経路のみ。
DPテーブルを初期化し、開始点を設定します
最初の行の経路数を計算します
最初の列の経路数を計算します
各セルの経路数を計算します
右下の値が答えです
from typing import List
class Solution:
def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
"""
障害物のあるグリッドでのユニークパス数計算
Args:
obstacleGrid: 障害物グリッド (0: 通路, 1: 障害物)
Returns:
ユニークパス数
Time Complexity: O(m*n)
Space Complexity: O(n) - 1D DP最適化版
"""
if not obstacleGrid or not obstacleGrid[0] or obstacleGrid[0][0] == 1:
return 0
m, n = len(obstacleGrid), len(obstacleGrid[0])
# 終点が障害物の場合
if obstacleGrid[m - 1][n - 1] == 1:
return 0
# 1D DP（空間最適化）
dp = [0] * n
dp[0] = 1 # スタート地点
for i in range(m):
# 各行の最初の列
if obstacleGrid[i][0] == 1:
dp[0] = 0
# 残りの列
for j in range(1, n):
dp[j] = 0 if obstacleGrid[i][j] == 1 else dp[j] + dp[j - 1]
return dp[n - 1]
# 可読性重視の2D DP版（参考実装）
class SolutionReadable:
def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
"""
2D DP実装（理解しやすい版）
Time Complexity: O(m*n)
Space Complexity: O(m*n)
"""
if not obstacleGrid or obstacleGrid[0][0] == 1:
return 0
m, n = len(obstacleGrid), len(obstacleGrid[0])
# 2D DPテーブル初期化
dp = [[0] * n for _ in range(m)]
dp[0][0] = 1
# 最初の行を初期化
for j in range(1, n):
dp[0][j] = 0 if obstacleGrid[0][j] == 1 else dp[0][j - 1]
# 最初の列を初期化
for i in range(1, m):
dp[i][0] = 0 if obstacleGrid[i][0] == 1 else dp[i - 1][0]
# メインのDP計算
for i in range(1, m):
for j in range(1, n):
if obstacleGrid[i][j] == 1:
dp[i][j] = 0
else:
dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
return dp[m - 1][n - 1]各セルを1回ずつ処理
1D DP配列のみ使用
| 手法 | 時間計算量 | 空間計算量 | 可読性 | 実装難易度 |
|---|---|---|---|---|
| 1D DP (採用) | O(m×n) | O(n) | ★★★☆☆ | ★★★☆☆ |
| 2D DP | O(m×n) | O(m×n) | ★★★★★ | ★★☆☆☆ |
| 再帰+メモ化 | O(m×n) | O(m×n) | ★★★★☆ | ★★★★☆ |
| DFS/BFS | O(2^(m+n)) | O(m+n) | ★★★☆☆ | ★★★☆☆ |