動的計画法が苦手な人が、動的計画法が超苦手な人へアドバイスしてみる

TopCoder

この記事は、Competitive Programming Advent Calendar Div2013（http://partake.in/events/3a3bb090-1390-4b2a-b38b-4273bea4cc83）の8日目の記事です。

動的計画法(Dynamic Programming, DP)についての記事です。

12/9 前編にサンプルプログラム（http://ideone.com/2B7f4v）を追加しました
12/11 前編の図２つを差し替えました。

はじめに

まずは、本やネットの資料で、動的計画法についてのすばらしい解説はいろいろありますので、まずはそれらを参考に。

  • プログラミングコンテストでの動的計画法
  • 最強最速アルゴリズマー養成講座：アルゴリズマーの登竜門、「動的計画法・メモ化再帰」はこんなに簡単だった

でも、苦手な人視点からのアドバイスはあまりない気がするので、敢えて書いてみることにしました。ただ、

  • 自分以外は誰も悩まなかったポイントかもしれません。
  • すこしはコツみたいなことも書いてますが、負け組の考え方である可能性は高いです。
  • よって変な癖とかついてしまうかもしれません。

でも、そこはうまく取捨選択してください。というか、むしろ、良い考え方を教えてほしいですorz

対象の読者
  • 動的計画法の基本的な問題（0-1ナップザックとか）は、何をやってるかは理解できる。
  • プログラミングコンテストチャレンジブック第2版のP52-P55は理解できる
  • 自力で動的計画法の問題を解くのは、ほぼ不可能。
  • 動的計画法はイメージ？何をイメージしたらいいの？DPテーブルの値が決まってく様子？分からん！
  • そもそも漸化式が思いつかないので、イメージ以前の問題
  • DPテーブル、変数に何を使えばいいのか、さっぱり分からん
  • 動的計画法は中学受験算数の出題範囲→そんなの一般人はやらない。来世に期待！
  • 上位の人「DPに逃げました」→ハラスメント
お断り
  • 基本的に、プログラミングコンテストチャレンジブックの用語を使います。
    • 動的計画法での計算結果を保存する変数を「DPテーブル」と呼び、配列変数の名前をdpとします。
    • 「メモ化再帰」「漸化式」等の用語も、そのまま使います。

前編：再帰のやり方とか知ってるのに、どうも「メモ化再帰」がしっくりこないあなたへ

※ 前編で登場する、「枝刈り探索」と「メモ化再帰」のサンプルプログラムです→（http://ideone.com/2B7f4v）あわせてご利用ください。
動的計画法の問題で求めるのは、たいてい次のA,Bだと思います。

A. 最小値・最大値を求める
B. 数え上げ。何個か何パターンかを求める

自分の場合は、こういうのを求めるとき、仕事でも日常生活でも、以下のような手順で考えていました。

(1) 選択肢を羅列する
(2) 制約条件があるなら、選択肢が制約条件を満たすかチェックする。
(3) A. 制約条件を満たしたやつの中での最大値を求める。
　　B. 制約条件を満たしてたら+1して数えていく。

ただ、この手順は、動的計画法（≒メモ化再帰）的な考え方とは、かけ離れているのですよ…。例えば以下の問題を考えてみましょう。

0-1ナップザック問題（プログラミングコンテストチャレンジブックより）
重さと価値がそれぞれ、wi,viであるようなn個の品物があります。これらの品物から、重さの総和がWを超えないように選んだ時の価値の総和の最大値を求めなさい。
1≦n≦100, 1≦wi,vi≦100, 1≦W≦10000

入力例
n=3, (w,v)={(2,3), (3,4), (1,2)}, W=3

「全探索が基本」「樹形図をかけば分かる」というのは、知ってたので、自分は以下のように考えました。

これは「メモ化再帰」ではありませんし、ここから「メモ化再帰」に改良することすらできません。確かに最大値も求まっているし、これでも良い気もしますが、すぐにn≦100という条件をみて、

n=100のとき、2^100通り→こんな問題解けるわけがない→そっとじ

とやってました…。「メモ化再帰」のように、状態の少なさを生かした高速化ができなくなります。

あと、こんな発想をするタイプの人にとっては、「(2) 制約条件があるなら、選択肢が制約条件を満たすかチェックする。」は、単にひと手間を複雑にしているだけの邪魔者にしかみえないでしょう…。制約条件は、動的計画法のともだちなんですよ…。（後編で説明します。）

「メモ化再帰」とは、以下の図のようなかんじです。根のほうにデータを集めるような樹形図です。先ほどの図とはデータの流れが真逆なことが分かるでしょう。

ちなみに、「メモ化再帰でない全探索」のあと、少し成長しました。制約条件を破ってたら、以下の図のように、もう計算しないようにしましたが…

「メモ化再帰」では、枝先のほうをまとめて端折っているし、似たような樹形図を見かけますが、これでも「メモ化再帰」とは違います！！ これは、俗にいう「枝刈り探索」です。「メモ化再帰」と「枝刈り探索」を比較してみました。

「メモ化再帰」

    • int func(int x, int y)のように、関数は値を返す
    • 根のほうにデータを集める樹形図。
    • 同じ入力値をこの関数の結果を返す、int memo[x][y]のようなメモ用の配列変数がある。
    • 計算をはしょれるのは、入力x,yのときの出力（返り値）を、既に知ってるから。
    • 計算量が予測しやすい。「メモ用の配列変数の要素数（入力するx,yのパターン数）」*「関数内の計算量」

「枝刈り探索」

    • void func(int x, int y)のように、関数は値を返さなくてよい。
    • 枝のほうにデータが流れていく樹形図、それを集計するかんじ。
    • 今まで呼んできた関数（根のほう）での計算結果を、グローバル変数などに保存しておいて（上記の例だと、どの品物を今まで選んできたか）、それを生かすことが多い。
    • 計算をはしょれるのは、制約条件を既に違反してたり、最大値・最小値をもう達成することが不可能なため、先の関数を呼ぶ必要がないから。
    • 計算量が予測しにくい。

逆に、両者の共通点といえば、「深さ優先探索(Depth First Search)で全探索する」部分ですね。後はいろいろ違うのでごっちゃにしないようにしてください。どちらかが優秀という訳ではないです。同じように混乱したことがある人は、プログラミングコンテストチャレンジブック第２版のP54のCOLUMN、「全探索の書き方」もぜひ読んでください。

メモ化再帰については、先ほど示した資料も含め、良い資料がたくさんあるので、説明は省きます。Have fun and good luck!

後編：動的計画法の意味はわかるけど、問題は解けません！なあなたへ

動的計画法の嫌なところ

  • バリエーションが豊富すぎて、手におえない。
  • どこから手をつけたらいいか分からない。

バリエーションが豊富すぎて、手におえないのは、しょうがないです。ただ、そのバリエーションの多さに、基本的なことの検討を見逃して、動的計画法の割には簡単な問題をおとしてしまうのは、避けたいです。
あと、どこから手をつけたらいいか分からない問題について。DPで問題を解くためにクリアするべき点が3つあります。

  • (1) DPテーブルの定義 dp[?][?]=?
  • (2) 漸化式をたてる
  • (3) 状態・計算量を減らしてみる

これらが、(1)→(2)→(3)のように、順番にクリアしていくことができればいいのですが、多くの問題の場合は(2)ができないので(1)を直すとか、(1)を変えたら(3)の計算量が増えたとか、3つとも複雑に絡み合うので、やっかいなんですよね…。まぁ、1つずつ見ていきたいと思います。

(1)DPテーブルの定義 dp[?][?]=?
  • まずは基本的な形から検討しましょう。
    • 一番の基本は、「dp[?][?]=問題で求めるもの（最大値とか個数とか）」です。まずは、これから検討しましょう。これが通用しない場合もあるのですが、それでも基本から検討しましょう。
    • インデックスのほうで、dp[0番目〜i番目までの何か]のように、何かの番号がくることが多いです。
  • DPテーブルの定義のバリエーションは、無限にあるわけではない
    • 問題に出てくる変数の種類はせいぜい2種類〜5種類程度です。例えば、ナップサック問題だったら、重さ・価値・品物番号の３種類です。dp[番号][重さ]=価値とか、dp[番号][価値]=重さとか、いろいろつくれますが、それでも無限にあるわけではないです。がんばれ！
  • 変数の定義はちゃんとしましょう。
    • 動的計画法とは、直接関係ないのですが、変数の定義をちゃんとするのは、動的計画法では特に重要な気がします。結構、人によって、要素が1個ずれてたり（iがi+1になったりi-1になったり）ということはあるのですが、それは変数の定義が違うからですが、ちゃんと漸化式とつじつまがあってれば正解になります。
    • 具体例1 ナップサック問題
      • × dp[品物番号i][重さ]=価値
      • â—‹ dp[品物番号i][0〜i-1番目までの重さ]=0〜i-1番目までの価値の合計 （特に0〜i-1とか範囲の部分が重要）
    • 具体例2 SIRO Challenge http://jag2013autumn.contest.atcoder.jp/tasks/icpc2013autumn_c
      • × dp[訪問都市（ビットで）][現在いる都市]=時間
      • â—‹ dp[ラーメン屋のある訪問した都市（ビットで）][現在いる都市]=スタート地点から現在の都市までの移動時間＋現在いる都市でラーメン食べる時間も含めた合計時間
  • 複数の解法がありうるので、ちょっと無駄な要素があってもOKな場合がある。
    • O(n^2)のDPだけど、O(n^4)でもOKみたいな問題もあります。メモリ・計算量の許すのであれば、ちょっとぐらい無駄な要素があってもOKです。分かりやすい、書きやすいほうを選びましょう。
  • DPの配列に慣れましょう。
    • 動的計画法で、出てくる配列は、dp[100000][4][4][4]とか、dp[50][50][50][50]とか、日常プログラミング生活では、あまり見ないような配列がでてくることがあります。メモリ・計算量の許す限り、どんな形でもとりうるので、念頭に置いておきましょう。
(2) 漸化式をたてる
  • まずは基本から
    • kinabaさんの昔の記事にあるとおり、http://www.kmonos.net/wlog/90.html#_1712081024、dp[x][y]と定義したら、dp[x][y]とdp[x-1][y]、dp[x][y]とdp[x][y-1]にどういう関係があるかというのを着目したほうが良いと思います。例外は腐るほどあるのですが、例外から考えるとバリエーションがあまりに多すぎて死にます。まずは基本から検討しましょう。
  • 確率のほうがやりやすい
    • 確率問題は、わりと自然と漸化式がでてきやすい気がします。1/3の確率で+100点、2/3の確率で-50点だったら、dp[turn+1] = (dp[turn]+100)/3 + (dp[turn]-100)*2/3 のように、確率の公式そのものが漸化式になりうるので。
  • 法則を見つけるコツ
    • 小さいケースで考えてみる（n=1,n=2,n=3のときとか）
    • 樹形図を書くと、法則が見えてくることもある。SRM531 DIV1 Easy NoRepeatPlaylistが好例
    • 分割する。範囲DPや、グループ分けするようなビットDPでは、dp[全体]は、dp[分割した部分1]とdp[分割した部分2]の関係式で表せることが多いです。用語「最適性原理」も一度はチェックしてみてください
(3) 状態・計算量を減らしてみる

「状態」とは、DPテーブルでいったらdp[x][y]、再帰関数だったら int dfs(int x, int y)の(x,y)の組み合わせのことを指します。状態が多すぎると、計算時間が間に合わないので、解けません。どんな減らし方があるか書いてみました。

  • 制約条件
    • まず、制約条件が重要です。例えば、ナップサック問題で、「重さ≦1000000、価値≦100」という条件をみたら、「価値の範囲が狭い」→「dp[価値]のようにDPテーブルを定義したら、うまくいくのでは？」と思いましょう。
  • 結果が同じになる状態はないか？
    • 例えば、dp[100000000000]と、状態が無数にあるような場合でも、例えば、インデックスが奇数・偶数で値が同じになるなら（dp[0]=dp[2]=dp[4]=...、dp[1]=dp[3]=dp[5]=...）となるなら、dpテーブルはdp[2]で十分になります。
    • 周期性、鳩の巣原理、偶数奇数のような法則があれば、結果が同じになる状態があるはずです。状態を減らすチャンス！
  • もう古い状態は無視できるのではないか？
    • 例えば、3手前以前に何の手をうったかは影響ないのであれば、dp[手数][2手前][1手前][現在]という風に削ることもできます。
    • プログラミングコンテストチャレンジブックP177「ドミノ敷き詰め」のように、上から順番に埋めてって、もう下のドミノに影響を与えないような上部内側の部分も、無視できますね。
  • 中は無視して、端だけで良いのでないか？
    • 区間DPは典型例です。例えば文字列を使う問題なら、dp[左端][右端]としただけで、文字列が定まります。dp[左端][右端][上端][下端]とやれば、2次元の範囲が定まります。
  • 「順序あり O(n!)」 → 「順序なし+現在位置O(n*2^n)」、「順序なしO(2^n)」→「個数・最大値・最小値 O(n)」と、計算量を落とせないか考える
    • 「順序あり O(n!)」 → 「順序なし+現在位置O(n*2^n)」については、巡回セールスマン問題等で使うテクニックです。最小移動時間を求めるのに、dp[3→2→7→5]ã‚‚dp[2→3→7→5]ã‚‚dp[7→3→2→5]も、同じ状態とみなして良いです。なぜなら、これらから次の都市も含めた場合の最小移動時間を求めるときに、どうたどってきたかを知る必要はなく、すでに通過した都市（順序なし）と、現在いる都市が分かれば、次の都市を選べるからです。
    • 「順序なしO(2^n)」→「個数・最大値・最小値 O(n)」で計算量を落とせることもありますが、見破るのはかなり難しいことも。例題としては、SRM511 DIV1 500pts FiveHundredEleven。
  • (1)に戻って、dpテーブルの定義を見直せば、状態を減らせるかも。
    • 「○○がX以下で，△△を最大化しなさい　→　△△がいくらまでなら，○○の最小値はX以下になるか？」の置き換えで、配列のインデックスと、配列の値を交換することができます。

おわりに

  • メモ化再帰と枝刈り探索は、違います。普段、枝刈り探索っぽい考え方をしている人は、頭を切り替えましょう。
  • 動的計画法は、問題のバリエーションが多いのですが、まずは基本的なところから検討しましょう。
  • 企画倒れ感のある内容になってしまいました。超苦手な人向けになってない気がします。
  • 他の方のフォロー記事に期待！