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

hamayanhamayan's blog

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

競技プログラミング

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

入門者向け

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

入門問題

最大最小系
dp[] := その条件下での最大値・最小値

yes/no系
dp[] := その条件下でのtrue/false

組み合わせ系
dp[] := その条件下での組合せ数

より強くなるために

テク一覧

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

中難易度問題（工事中）

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

最大最小系

yes/no系

組み合わせ系