Longest Common Subsequence
最長共通部分列 (LCS) - 動的計画法 の典型問題
1. 動的計画法 (Dynamic Programming)
時間計算量 : O(m * n) LCS を計算 する最 も一般的 な解法 。ここで
mとnはそれぞれ2つの文字列 の長 さ。m * nの DP テーブルを計算 し、各 セルを埋 める必要 がある。空間計算量 : O(m * n) 各部分問題 の解 を格納 するために
m * nの DP テーブルが必要 。
2. 空間最適化動的計画法 (Space Optimized DP)
時間計算量 : O(m * n) 基本的 な動的計画法 と同 じだが、現在 と前 の行 の情報 のみを保持 。
空間計算量 : O(min(m, n)) 通常 2行 で DP テーブルを表現 し、交互 に更新 。
3. 再帰 (Recursive)
時間計算量 : O(2^(m + n)) 最 も直接的 な解法 。各再帰 で2つの選択肢 があり、指数的 な時間計算量 になる。
空間計算量 : O(m + n) 再帰 の深 さが最大
m + nなので、空間計算量 は再帰 の深 さ。
4. バックトラッキング (Backtracking)
時間計算量 : O(2^(m + n)) 純粋 な再帰解法 と同様 。
空間計算量 : O(m + n) バックトラック処理 で経路 を格納 するための追加空間 を使用 。
5. メモ化再帰 (Memoization / Top-Down DP)
時間計算量 : O(m * n) 動的計画法 と同 じ。メモを使用 して重複計算 を回避 。
空間計算量 : O(m * n) メモを格納 するために追加 の
m * n空間 が必要 。
6. 行列法 (Matrix Method)
時間計算量 : O(m * n) 基本的 な動的計画法 と同 じ。
空間計算量 : O(m * n)
Summary
| 解法 | 時間計算量 | 空間計算量 |
|---|---|---|
| 動的計画法 | O(m * n) | O(m * n) |
| 空間最適化 DP | O(m * n) | O(min(m, n)) |
| 再帰 | O(2^(m + n)) | O(m + n) |
| バックトラッキング | O(2^(m + n)) | O(m + n) |
| メモ化再帰 | O(m * n) | O(m * n) |
| 行列法 | O(m * n) | O(m * n) |
- 動的計画法 は最 も一般的 で効率的 な解法
- 空間最適化 DPは時間計算量 に影響 を与 えずに空間消費 を大幅 に削減
- 再帰 とバックトラッキングは時間効率 が低 く、小規模入力 や問題理解 のための簡単 なデモに適 している