動的計画法 — 同じ計算を二度しない部分問題の重なりに気づくところから動的計画法を導きます。メモ化と表埋めの対応、適用できる 2 つの条件、状態数と遷移コストによる計算量の見積もり、直前の行だけ持つ空間圧縮、貪欲法との違いを扱います。