📋 問題概要
ロボットがm×nグリッドの左上角(0,0)から右下角(m-1,n-1)に移動する際の、 一意な経路数を計算する問題です。
- ロボットは右または下にのみ移動可能
- 制約: 1 ≤ m, n ≤ 100
- 結果は 2 × 10⁹ 以下が保証
🧮 数学的解法 (最適解)
💡 核心アイデア
この問題は組み合わせ数学の問題として解けます。
ロボットは合計 (m-1) + (n-1) = m+n-2 回移動し、
そのうち右に n-1 回、下に m-1 回移動します。
C(m+n-2, min(m-1, n-1))
これは「m+n-2回の移動のうち、右移動（または下移動）の回数を選ぶ組み合わせ」として表現できます。
⚡ 実装コード
import math
class Solution:
def uniquePaths(self, m: int, n: int) -> int:
"""
数学的解法による経路数計算
Time: O(1), Space: O(1)
"""
# 組み合わせ数 C(m+n-2, min(m-1, n-1))
total_moves = m + n - 2
right_moves = n - 1
down_moves = m - 1
# math.comb()はPython 3.8+のC実装で高速
return math.comb(total_moves, min(right_moves, down_moves))
def uniquePathsManual(self, m: int, n: int) -> int:
"""
手動実装版（Python 3.7以下対応）
"""
total_moves = m + n - 2
k = min(m - 1, n - 1)
result = 1
for i in range(k):
result = result * (total_moves - i) // (i + 1)
return result📊 計算例: m=3, n=7
計算過程:
総移動回数: 3+7-2 = 8
右移動回数: 7-1 = 6
下移動回数: 3-1 = 2
C(8, 2) = 8!/(2!×6!) = 28
📈 1次元動的プログラミング
💡 核心アイデア
2次元DPの空間計算量を最適化し、O(min(m,n))まで削減。 前の行の情報のみを保持することで実現します。
⚡ 実装コード
def uniquePathsDP1D(self, m: int, n: int) -> int:
"""
1次元DPによる実装
Time: O(m×n), Space: O(min(m,n))
"""
# メモリ効率化: 小さい方の次元で配列作成
cols = min(m, n)
rows = max(m, n)
# DPテーブル初期化
dp = [1] * cols
# 各行を処理
for i in range(1, rows):
for j in range(1, cols):
# dp[j] = 上から + 左から
dp[j] += dp[j - 1]
return dp[cols - 1]🎯 可視化デモ
ステップ: 0
📋 2次元動的プログラミング
💡 核心アイデア
最も直感的な解法。各セル(i,j)への経路数は、
dp[i][j] = dp[i-1][j] + dp[i][j-1] で計算。
⚡ 実装コード
def uniquePaths2D(self, m: int, n: int) -> int:
"""
2次元DPによる実装
Time: O(m×n), Space: O(m×n)
"""
# 2次元DPテーブル初期化
dp = [[0] * n for _ in range(m)]
# 初期化: 最初の行と列は全て1
for i in range(m):
dp[i][0] = 1
for j in range(n):
dp[0][j] = 1
# DPテーブル更新
for i in range(1, m):
for j in range(1, n):
dp[i][j] = dp[i-1][j] + dp[i][j-1]
return dp[m-1][n-1]🎯 可視化デモ
ステップ: 0
📊 アルゴリズム比較分析
⚖️ 計算量比較
| 解法 | 時間計算量 | 空間計算量 | 可読性 | 実装難易度 |
|---|---|---|---|---|
| 数学的解法 | O(1) | O(1) | 高 | 低 |
| 1次元DP | O(m×n) | O(min(m,n)) | 中 | 中 |
| 2次元DP | O(m×n) | O(m×n) | 最高 | 低 |
🚀 パフォーマンステスト
パフォーマンステストを実行してください
💡 選択指針
数学的解法 推奨
- 競技プログラミング
- 高速処理が必要
- メモリ制約が厳しい
1次元DP 推奨
- メモリ効率重視
- DPの学習目的
- 拡張性が必要
2次元DP 推奨
- 教育・学習目的
- 可読性最優先
- デバッグが必要
🎯 まとめ
📈 学習ポイント
- 問題の抽象化: 格子経路問題を組み合わせ数学で解く
- 空間計算量最適化: 2次元→1次元DPへの変換
- 数学的洞察: 動的プログラミングを数式で置き換え
- 実装選択: 用途に応じた最適解法の選択
🔧 実装のコツ
- 境界条件: 最初の行・列の初期化
- オーバーフロー対策: 整数演算の順序に注意
- メモリ最適化: 必要最小限のデータ構造使用
- 型安全性: 適切な型ヒントの活用