一般論
DP の解き方
- すぐに DP の式が生えてこない場合は、ほしい値からの再帰を考える
- DP の定義式（漸化式ではない）を書くようにする
- 初期値・遷移・ほしい値が何かを明確にする
- 初期値について
- 数え上げの場合: 0
- 最大化の場合: -∞
- 最小化の場合: +∞
典型的な問題
- 部分和問題
- 全体でK個以内の部分和問題
- 各要素個数制限なしの部分和問題
- 各要素個数制限ありの部分和問題
- ナップサック問題
- 個数制限なしナップサック問題
- 区間分割の最適化 (けんちょん本)
- 最長共通部分列問題（LCS）
- 編集距離
- 最大区間和
問題例
アルゴ式