動的計画法

概要

最小十分状態を定め、グリッド・容量・列・prefix分割・区間・部分集合という基本的な依存構造を比較する。桁上限・automaton・carryによる有限状態化まで一巡した後、確率とゲームで遷移の評価方法を変える。基本的なDP類型を学んでから遷移最適化と固定線形遷移の累乗へ進み、循環局面の後退解析へ広げる。後半は境界圧縮、Steiner木、巨大容量、期待値の状態削減、数ゲームの和を発展として扱う。列DPのLISと値域集約を比較し、automatonは文字列章、Steiner木は最短路の単元を先に参照する。

DP状態と遷移

未来に必要な情報を状態とし、遷移と基底を設計する。

考え方

DPは履歴を列挙する代わりに、未来の選択肢と評価が同じになる履歴を状態へまとめる方法である。状態の十分性、遷移の一意性、計算できる依存順を確定してから、遷移の共有や状態圧縮へ進む。

成立条件と計算量

計算量は到達状態数と実際の遷移数で数える。添字がbitmaskや区間であることだけでは依存順は決まらない。循環する遷移、確率の自己loop、巨大な資源量は、それぞれ専用の処理が必要になる。

章の構成

項目は各章の読書順に並べています。親子関係は順序と独立しているため、階層を字下げで表さず、子Unitには「概念上の親」を示します。導入項目は関連手法の見取り図で、発展的なUnitは対象色を目安に後から戻って学べます。

問題一覧

この単元に直接配置する問題はありません。下位単元または関連問題を参照してください。

各問題の解説は問題ごとの本文として執筆します。各項目には主題・追加で学ぶ技能・既習技能の役割を示します。

関連問題

前提・学習成果・出典

導入対象の目安: 緑色(800–1199)。状態・基底・遷移・計算順を明示する習慣を身につける入口。

対象色の読み方は本書の読み方を参照してください。

Canonical taxonomy: FinalTaxonomyBuild final-taxonomy-build-initial digest f1ae39bc7201c3374c108e800284e1e0068ce6f7a57f15b2a9e5219616e3c4fe / LearningUnit unit-chapter-dynamic-programming

習得する技能

  • 未来に十分な状態と、状態間の完全な遷移を説明できる。

前提と範囲

共通前提: prereq-abc-advanced-v1 (1.0.0)。

直接の前提単元: なし。

このUnitを直接前提とする単元: なし。

状態と遷移の設計を共通言語にし、集合・列・確率・ゲーム・遷移高速化へ進む土台を作る。

このUnitでは扱わないもの

  • なし

根拠