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

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)にできる