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

hamayanhamayan's blog

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

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

入門者向け

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

より強くなるために

テク一覧

1. オートマトン上でDPする手法がある
2. 選択するものを最初にソートしておくと、DPできたり、状態を同一化できたりする
3. 状態が全部必要ないので状態数が削減できる
4. 正しい括弧列(dyck列)の数え上げはカタラン数を関連がある 必要な問題 解説
5. dp[L][R][sm]をやる時は答えを更新していくことでdp[L][sm]だけで済む場合がある
6. 隣り合う要素の更新を入れることで最近だけの更新を考えるだけで良くなる
7. 尺取り法を応用した更新最適化がある
8. メモリが少ない場合での復元には再帰を使うテクがある
9. 区間を添え字として持つDPがある
10. 2つの順列の対応付けを行う箱根DPという典型がある
11. 文字列の部分列の個数を添え字に持つ典型
12. 縦と横は独立に計算できるため、O(WHN)をO(WN+HN+WH)にできる
13. 添字が負数になる場合は添字+baseをして、0をbaseにして使う
14. 境界線をうまく決めることで状態をまとめていく chokudaiさんの解説放送からの知見
15. 負の数を経由することで最適解が得られることがあるような問題は、最大最小の両方を保持しながらDPしていく
16. 配列を使い回すことでメモリ使用量を節約する(500^3は256MBに乗らない)
17. 遷移が多い場合は貪欲法を使うことで最適であろう遷移を絞ることができる

以下DPの問題(適当に分類、結構難しいのも含まれる)

最大最小系

yes/no系

組み合わせ系