動的計画法をまとめたもの
入門者向け
入門問題
最大最小系
dp[] := その条件下での最大値・最小値
- EDPC Frog 1 解説
- EDPC Frog 2 解説
- AOJ 0-1ナップサック問題
- yukicoder No.458 異なる素数の和
- ABC015 高橋くんの苦悩
- ABC 054 Mixing Experiment
- yukicoder No.472 平均順位
- yukicoder No.561 東京と京都 解説
- ARC090 Candies 解説
- ABC099 Strange Bank 解説
- HR 積み木 / Blocks 解説
- EDPC Knapsack 1 解説
- AOJ マルバツスタンプ 解説
yes/no系
dp[] := その条件下でのtrue/false
- yukicoder No.4 おもりと天秤
- yukicoder No.183 たのしい排他的論理和(EASY)
- ABC011 123引き算
- ARC075 Bugged
- yukicoder No.914 Omiyage 解説
組み合わせ系
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の問題(適当に分類、結構難しいのも含まれる)
最大最小系
- EDPC Vacation 解説
- AOJ パンケーキ 解説
- ABC100 Patisserie ABC 解説
- 【テク2】CF436 Fire 解説
- AtCoder 101 to 010 解説
- 【テク1】CF New Year and Old Subsequence 解説
- 【テク2】AC Zabuton
- 【テク6】【テク7】CF142 Towers 解説
- 【テク8】CSA65 Classic Task （復元がむずい）
- 【テク2】SRM610 AlbertoTheAviator 解説
- 【テク2】AC Zabuton
- AC 建物 解説
- 【テク11】CC Chef and Chefness
- yukicoder No.664 超能力者Aと株価予測 解説
- AC Many Go Round 解説
- 【テク13】yukicoder No.710 チーム戦 解説
- 【テク15】yukicoder No.505 カードの数式2 解説
- 【テク15】CC Algebra Score 解説
- AOJ しりとり圧縮 (Shiritori Compression) 解説
- AC Sum of Cards
- 【テク17】HR リンゴの出荷 / Apples 解説
- 【テク2】【テク16】yukicoder No.777 再帰的ケーキ 解説
- EDPC Knapsack 2 解説
- 【テク17】EDPC LCS 解説
- yukicoder No.783 門松計画 解説
- 【テク17】CF Jongmah
- 【テク2】yukicoder No.798 コレクション 解説
- 【テク17】LC1027 Longest Arithmetic Sequence 解説
- 【テク3】【テク17】yukicoder No.818 Dinner time 解説
- いろはちゃんコンテスト Day1 友達以上恋人以下 解説
- LC Partition Array for Maximum Sum
- 【テク20: 編集距離】ICPC JAG 国内模擬予選 2019 D 解説
- HUPC2019F グリッドの番号 解説
- AOJ イルミネーション 解説
yes/no系
組み合わせ系
- ABC130E Common Subsequence 解説
- ABC122 We Like AGC 解説
- AOJ Commute routes （組み合わせ系）解説1 解説2
- 【テク3】CF320 LCS Again 解説
- 【テク3】AC Limited Xor Subset
- yukicoder No.612 Move on grid 解説（添字に負の数が含まれる練習用）
- 【テク5】CF225 Antimatter 解説1 解説2 解説3
- ARC059 バイナリハック 解説
- AC Road of the King
- 【テク9】SRM728 Div1 Med IncreasingSequences 解説
- 【テク10】AOJ 箱根駅伝 解説1 解説2 解説3
- 【テク2】AOJ 僕の友達は小さい 解説1 解説2
- CSA69 Build Correct Brackets 解説
- 【テク12】CSA Binary Flips 解説1 解説2
- yukicoder No.663 セルオートマトンの逆操作 解説
- 【テク12】JOI abduction 解説
- RUPC2017 Day3 素因数分解の多様性 (The Diversity of Prime Factorization) 解説
- FHC2018 Round1 A Let It Flow 解説
- 【テク14】AC チーム分け 解説
- AC Not Too Close 解説 （多次元）
- 【テク16】ECR49 Inverse Coloring 解説
- AOJ 繰り返す呪文
- AC 半分 解説
- ABC113 Number of Amidakuji 解説
- AC Union 解説
- 【テク18】AOJ プレゼント (Presents) 解説
- 【テク3】AC クリスマスツリー (Tree Coloring)
- 【テク2】EDPC Tower 解説
- CF533 Ayoub and Lost Array
- 【テク2】【テク3】AC Modulo Operations 解説
- 【テク11】yukicoder No.840 ほむほむほむら 解説
- 【テク10】ABC134F Permutation Oddness 解説
