FreeStyleWiki

動的計画法問題思考フロー

[アルゴリズム,DP]

動的計画法問題思考フロー

  ナップサックDPの問題の思考フロー

  1. 問題の方向性を決定する
    1. 最大化問題: dpの配列は0埋め、漸化式の遷移はmax(a, b)
    2. 最小化問題: dpの配列はINFで埋める、漸化式の遷移はmin(a, b)
  2. 次元を決める
    1. データが1種類1次元: dp[i] コイン問題など
      1. 遷移がわかる表を書くことで漸化式が立ちやすくなる
    2. データが2種類2次元: dp[i][j] ナップサック問題など
      1. 遷移がわかる表(iが配置するモノへのインデックス, jが容量や価値の合計値など)を書く
    3. データが3種類3次元: dp[i][j][k] AtCoderのD問題はこれが多い
      1. 次元が上がり、イメージしにくい。iごとに表を複数書けばよさそう
    4. データがそれ以上: 4次元はあんまり出てないし、考え直した方がいいという声も
  3. 遷移と漸化式を考える
    1. dp[i] := dp[i-1] ... といった形、1重ループ
    2. dp[i][j] := dp[i-1][j] ... といった形、2重ループ
    3. dp[i][j][k] := dp[i-1][j][k] ... といった形、3重ループ
  • 漸化式の遷移について典型的なものに関してのヒント
    • 割り当てるモノの価値や重さが条件になって場合分けが発生する
    • 横軸を限界値、縦軸をモノへのインデックスとする
    • モノを割り当てるときに、「使う/使わない」を考える

  例題

問題 最大化 最小化 1次元 2次元 3次元 多次元 解いた? メモ
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 解説を読んでもしっくりこなかった。2次元DPのわりに遷移が他と違う感じ。