動的計画法の計算量 — 空間を時間と交換
動的計画法が指数問題を多項式時間に削減する仕組みを理解します。メモ化、タブレーション、状態空間分析、古典的なDP問題をカバー。
Analysis Concepts
詳細な説明
動的計画法が計算量に与える影響
**動的計画法（DP）**は、重複する部分問題に分解し、その結果をキャッシュすることで問題を解く技法です。
古典的な例：Fibonacci
| アプローチ | 時間 | 空間 |
|---|---|---|
| ナイーブ再帰 | O(2ⁿ) | O(n) |
| メモ化（トップダウン） | O(n) | O(n) |
| タブレーション（ボトムアップ） | O(n) | O(n) |
| 空間最適化版 | O(n) | O(1) |
DP計算量の分析
DP解の時間計算量は：
時間 = (ユニークな状態数) × (状態あたりの作業量)
メモ化 vs タブレーション
- メモ化（トップダウン）: キャッシュ付き再帰。実際に必要な状態のみ計算。
- タブレーション（ボトムアップ）: 反復的にテーブルを埋める。再帰オーバーヘッドがなく、キャッシュ効率が良い。
ユースケース
動的計画法は、競技プログラミング、バイオインフォマティクス（配列アライメント）、自然言語処理（Viterbiアルゴリズム）、オペレーションズリサーチの最適化問題に不可欠です。