はまやんはまやんはまやん

hamayanhamayan's blog

競技プログラミングにおける動的計画法問題まとめ

動的計画法をまとめたもの

入門者向け

  • まずは「最大最小系」「yes/no系」「組み合わせ系」
  • 基礎はこことかこことかこことかで勉強しよう
  • ループで書くか、再帰関数かというのがあるが、こっちの方が書きやすいとかがあったりするので、どちらも書けるようになるのがオススメ

より強くなるために

テク一覧

1. オートマトン上でDPする手法がある
2. ナップサックとかの場合に選択順をうまくやることで状態を同一視できる場合がある
3. 状態が全部必要ないので状態数が削減できる
4. 正しい括弧列(dyck列)の数え上げはカタラン数を関連がある 必要な問題 解説

以下DPの問題(適当に分類)

最大最小系

yes/no系

組み合わせ系