漸化式を用いた動的計画法の関数の作り方
わんちゃんかわいいですね。
動的計画法勉強中で流れを掴むために関数の作り方を整理します。そのため間違った内容などもあるかもですがまとめてみます。
もし、間違っていたらコメントください。
動的計画法とは
分割統治法：部分問題を解き、その結果を利用して、問題全体を解く
メモ化：部分問題の計算結果を再利用する
動的計画法の種類
for文を用いたボトムアップ方式と、再帰を使ったトップダウン方式があると思っている。 今回はボトムアップ方式にフォーカスしてみる。
例: フィボナッチ数列
フィボナッチ数列の場合、N番目の値は(N - 1)番目と(N - 2)番目の値の和になっている。この場合、for文を用いてNが小さい値から埋めていく事ができ、その後の処理は以前計算した結果を再利用するという方針が立てられる。
動的計画法を立てるステップをまとめてみる。
動的計画法の立て方
題材はAtCoderの問題。
C: 節制 - AtCoder Beginner Contest 013 | AtCoder
はじめ、高橋君の満腹度は H です。N 日間のそれぞれの日について、その日にとる食事を次の 3 種類の中から 1 つ選びます。
・普通の食事: A 円の出費をして、満腹度が B 増える。
・質素な食事: C 円の出費をして、満腹度が D 増える。（ただし、C<A かつ D<B）
・食事抜き: 出費なしで、満腹度が E 減る。
厳しく節約すれば出費を抑えることができますが、あまりに節約しすぎて体調を崩してしまってはいけないため、N 日間で一度も満腹度が 0 以下にならないようにしなければなりません。
高橋君は最低何円の食費で N 日間を乗り切ることができるでしょうか？
この問題における30点解答を考える。
Step1 全列挙は可能か否か
問題を整理すると、「普通の食事」「質素な食事」「食事抜き」の３つの選択肢の内、毎日どれか１つを選ぶ。これをN日間まで繰り返した時に、最小の費用はいくらになるかというものである。まずは、全てのパターンを考えてみる。１日目は３つ選択肢があるので通り数は３通り。２日目は１日目で選んだものに対して同じく３つ選択肢があるので、ここまでで３2 = 9通り。これをN日間繰り返すと全列挙するためには(３N)通り存在する。これはNが大きな数字になれば処理しきれない。
つまり、全列挙不可能である。Step2へ。
Step2 部分問題を解き、その結果を用いる事で求めたい値が求まるか
今回の問題をもう少し深く整理する。この問題の主人公は、１日目に取った行動によって２日目の状態が決定する。具体的に説明すると、１日目に「質素な食事」という選択をしたとする。すると２日目が始まった時点では、主人公の満腹度はDだけ増え、経費はCだけ増える。少し抽象度をあげると、N日目の状態はN-1日目の行動によって変動する。逆に言うとN-1日目の行動はN日目に反映されることになる。
これは部分問題(N-1番目)を解き、その結果を用いることで求めたい値(N番目)が求まるといえる。Step3へ。
Step3 求めたい値を算出する際の主人公の状態を表すパラメータを列挙する
ここからが具体的な動的計画法の立て方になる。
求めたい値を算出するにあたり必要なパラメータを列挙する。 問題を確認すると、求める値は最小の「費用」になる。また、その時の主人公の状態を表すパラメータは、以下の２つ。
- 主人公が今、何日間すごしたか
- 主人公の今の満腹度
具体的には、「主人公が満腹度７０で３日目に到達した時の費用」という具合になる。
まとめると
- 求めたいもの: 「費用」
- その時の状態: 「何日目」と「満腹度」
上記を頭に置いときながらStep４へ
Step４ メモ化テーブルを作る
メモ化テーブルとは、ある状態の時の求めたい値を保持しておくためのテーブルである。ほとんどの場合、配列を使用する。
例えばフィボナッチ数列の場合、メモ化テーブルは以下のようになる。
| 配列のindex | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|---|
| 値 | 0 | 1 | 1 | 2 | 3 | 5 | 8 | 13 |
配列を使用した場合、主人公の状態を表すパラメータと配列のインデックスを対応させ、その時の求めたい値をそのインデックスに保存する。
今回の問題では主人公の状態を表すパラメータは「何日目」と「満腹度」の２つあるので、用意する配列は２次元配列になる。メモ化テーブルの配列名をdpとするとdp[何日目][満腹度] = 費用という使い方をする。
何日目かという情報をday、満腹度を今残っている体力と捉えてlife、費用をexpenceと置くとdp[day][life] = expenceと書ける。
ここまで用意できらたStep５へ
Step５ メモ化テーブルを用いて漸化式を立てる
漸化式とは、各項がそれ以前の項の関数で求まることを意味した等式である。例えばフィボナッチ数列の第５項目が求める関数をf(5)とするとf(5) = f(4) + f(3)と書くことができる。これを一般化すると
フィボナッチ数列の漸化式
f(n) = f(n-1) + f(n-2)
と書ける。これを今回の問題の「普通の食事」をした場合に当てはめてみる。
普通の食事: A 円の出費をして、満腹度が B 増える。
dp[day + 1][life + B] = dp[day][life] + A;
細かく見ていく。まず大前提としてdpに保存する値は「費用」であるということ。つまりこれは「費用」を求める式である。
次に「何日目day」に着目する。dp[day + 1](day + 1日目の費用)はdp[day](day日目の出費)によって決まる。今回は「普通の食事」をしているので、費用はA円かかる。つまり、dp[day]を「今日」と解釈しdp[day+1]``は「明日」と捉えた場合、今日の費用にA円払った状態が明日の費用になる。ここまでまとめると
dp[day + 1] = dp[day] + A
となる。次に「満腹度life」に着目する。明日の満腹度は今日どんな食事をしたかによって決まる。今回は普通の食事をしたので、満腹度はBだけ上昇する。よって今日の満腹度にB加えたものが明日の満腹度になる。以上をまとめると
dp[day + 1][life + b] = dp[day][life] + A
と書ける。これがこの問題における「普通の食事」を選択した場合の漸化式である。このように「質素な食事」「食事抜き」のパターンの漸化式を求めると以下になる。
今回は３パターンあるが、最終的に求めたいものは最小費用のもの。dp[day][life]を埋める時に常に費用が最小のもので埋めたい。そこで以下のように代入先に元々保存されていた費用と比べて小さい物を採用し更新していく。
これで漸化式は完成。
Step６ 材料を元に関数を設計する
関数の設計は以下のような感じになる。
ステップは以下の通り。これまでの準備がしっかりできていれば書けるはず。
- dpテーブルの初期化(状態をすべてカバーできるように容量を決めてあげる)
- 全ての状態を列挙できるようにfor文を使う
dpを初期化した時の全てのindexを網羅するようにfor文を作れば大体OK - for文の中に漸化式を記述
この時問題に応じてif文を用いて条件を制限する - 最終的に求めたいものをdpから取り出す
以上。
