動的計画法問題思考フロー
ナップサックDPの問題の思考フロー
- 問題の方向性を決定する
- 最大化問題: dpの配列は0埋め、漸化式の遷移はmax(a, b)
- 最小化問題: dpの配列はINFで埋める、漸化式の遷移はmin(a, b)
- 次元を決める
- データが１種類１次元: dp[i] コイン問題など
- 遷移がわかる表を書くことで漸化式が立ちやすくなる
- データが２種類２次元: dp[i][j] ナップサック問題など
- 遷移がわかる表(iが配置するモノへのインデックス, jが容量や価値の合計値など)を書く
- データが３種類３次元: dp[i][j][k] AtCoderのD問題はこれが多い
- 次元が上がり、イメージしにくい。iごとに表を複数書けばよさそう
- データがそれ以上: ４次元はあんまり出てないし、考え直した方がいいという声も
- データが１種類１次元: dp[i] コイン問題など
- 遷移と漸化式を考える
- dp[i] := dp[i-1] ... といった形、１重ループ
- dp[i][j] := dp[i-1][j] ... といった形、２重ループ
- dp[i][j][k] := dp[i-1][j][k] ... といった形、３重ループ
- 漸化式の遷移について典型的なものに関してのヒント
- 割り当てるモノの価値や重さが条件になって場合分けが発生する
- 横軸を限界値、縦軸をモノへのインデックスとする
- モノを割り当てるときに、「使う/使わない」を考える
例題
| 問題 | 最大化 | 最小化 | １次元 | ２次元 | ３次元 | 多次元 | 解いた？ | メモ |
|---|---|---|---|---|---|---|---|---|
| Educational DP Contest - A Frog1 | ○ | ○ | AC#8509011 | |||||
| Educational DP Contest - B Frog2 | ○ | ○ | AC#8520538 | |||||
| Educational DP Contest - C Vacation | ○ | ○ | AC#8534617 | |||||
| Educational DP Contest - D Knapsack 1 | ○ | ○ | AC#8441780 | 一番一般的な動的計画法の問題 | ||||
| AtCoder Beginer Contest 004 - D マーブル | ○ | ○ | AC#1935144 | |||||
| AtCoder Beginer Contest 015 - D 高橋くんの苦悩 | ○ | ○ | AC#8629344 | AtCoder Beginner Contest 015 | ||||
| AtCoder Beginer Contest 044 - C 高橋君とカード | ○ | ○ | ||||||
| AtCoder Beginer Contest 054 - D Mixing Experiment | ○ | ○ | ||||||
| AtCoder Beginer Contest 099 - C Strange Bank | ○ | ○ | AC#8543934 | 解説を読んでもしっくりこなかった。２次元DPのわりに遷移が他と違う感じ。 |