動的計画法の可視化
動的計画法は小さい部分問題を定義し、依存に沿った順序で解き、答えを再利用して重複計算を避けます。このコース群は小さな重複から始め、最適化問題の表の作り方へ進みます。
漸化式だけを覚える前に、一セルの意味、読める旧状態、書き込み順がその読み取りを可能にする理由を説明します。
動的計画法のレッスンの見方
三つを確認します。
- 状態の意味：フィボナッチの
dp[i]はfib(i)、LCS のdp[i][j]は二つの接頭部分の最長共通部分列長、編集距離の同じ形のセルは最少編集数です。0/1 ナップサックのdp[i][w]は最初のi品を容量wで選ぶ最大価値です。 - 読む旧状態：フィボナッチは左の二セル、LCS は上・左・左上、編集距離は三方向と操作費用を使います。ナップサックは前行と、その小さい容量の位置を読みます。位置が違えばアルゴリズムも変わります。
- 復元するもの：最終値だけで足りる問題もあれば、LCS やナップサックのように逆向きにたどって列や選択を復元する問題もあります。
計算量の比較
| レッスン | 状態の形 | 中心の考え | 時間 | 表示する領域 |
|---|---|---|---|---|
| フィボナッチとメモ化 | 再帰木／一次元表 | 重複する部分問題 | メモ化後 O(n) | O(n) |
| 両替 | 一次元表 | 複数の硬貨から最小を選び、貪欲法と比べる | O(amount * coins) | O(amount) |
| 最長共通部分列 | 二次元の接頭部分表 | 二文字列を整列し、逆にたどる | O(m * n) | O(m * n) |
| 編集距離 | 二次元の接頭部分表 | 挿入・削除・置換の最短手順 | O(m * n) | O(m * n) |
| 0/1 ナップサック | 二次元表 | 容量内で取るか取らないか | O(n * capacity) | O(n * capacity) |
フィボナッチは記憶の効果、両替は複数候補、LCS は第二の入力軸、編集距離は隣接状態の操作上の意味、ナップサックは選択の制約を示します。
推奨する学習順序
フィボナッチとメモ化で、再帰木の同じ呼び出しを確認し、キャッシュで取り除きます。ボトムアップへ切り替えると、木が一列のセルになります。
次の両替は一セルで複数の硬貨から最小を取ります。先に貪欲法を動かし、最大額から取る規則の失敗を見ます。硬貨の復元は、ナップサックへの準備にもなります。
最長共通部分列の二軸は文字列の接頭部分です。一致する文字は左上の答えを延ばし、不一致なら上か左の長い方を保ちます。右下の長さを文字へ復元し、同じ最適値でも別の有効な部分列が得られることを確認します。
編集距離は同じ格子を使い、上・左・左上を削除・挿入・置換に対応させます。右下の数だけでなく最短手順を復元し、再生して目標文字列になるかを検証します。
最後の 0/1 ナップサックでは右下が価値、逆向きの追跡が品物を示します。前行だけを読むことで同じ品を再利用しません。状態の定義が制約も守ります。
動的計画法の可視化一覧
漸化式を一段階ずつ進め、複雑な画面で止めて、セルの意味と参照した旧回答を説明してください。