動的計画法とは

動的計画法（どうてきけいかくほう、英: Dynamic Programming, DP）は、計算機科学の分野において、アルゴリズムの分類の1つである。対象となる問題を複数の部分問題に分割し、部分問題の計算結果を記録しながら解いていく手法を総称してこう呼ぶ。

　上記の説明はWikipediaからの引用だが、アルゴリズムはその定義を言葉で聞いただけではすぐに理解できない（よね？）。私も最初に「動的計画法は小さな問題をあらかじめ解いておき、その計算結果を利用する」と何かで動的計画法の説明を読んだ時に「？？？」となった。その後、自分で実装してみて初めて理解できたのでアルゴリズムにおいては自分で実装してみることが理解への近道のように感じる。

今回すること

　フィボナッチ数列を例に用いる。まずは単純な再帰関数による実装の限界を示し、そのあとに動的計画法の威力を実装によって示すという流れ。
　言語はC++を用いるが予備知識が必要になるほどではないはず（でもif文、for文、配列とかの知識は前提で進めます）。

フィボナッチ数列とは

　前２項の和を続けていく数列で、{1, 1, 2, 3, 5, 8, 13, ...}と続いていく。漸化式による表現では、

a_{n} = a_{n-1} + a_{n-2} (a_1 = 1, a_2 = 2, n\geqq 3)

のようになる。$a_0 = 1, a_1 = 1$とするときもある。フィボナッチ数列には今回触れないが面白い性質がたくさんあるので調べてみてほしい。

再帰関数による実装

　さて、早速実装してみる。上記のような漸化式を取るので、素直に再帰関数で実装すると次のようになる。

int fib(int n) {
  if (n == 0 || n == 1) return 1;

  return fib(n - 1) + fib(n - 2);
}

　図にするとこんな感じで再帰関数が呼び出されることになる(n = 4のとき)。

　しかし、お気づきになっただろうか…？上の画像ではfib(4)でfib(3)とfib(2)とを呼び出すが、fib(3)の時に再びfib(2)を呼び出していることに…。今回はn = 4という小さな数字だったから良かったが、これが大きな数になると同じ処理が何度も繰り返され、爆発してしまう。

　そこで登場するのが動的計画法！同じ処理をするのであれば、一度した計算を記録しておけばいいというのが冒頭に出てきた「動的計画法は小さな問題をあらかじめ解いておき、その計算結果を利用する」というものである（ここでストンときてくれると嬉しい）。

動的計画法による実装

　いよいよ動的計画法である。あらかじめ行った計算結果の記録には配列を用いる。

int f[100]; //配列の大きさは求められるnによって適宜変える
f[0] = 1;
f[1] = 1; //初項を用意しておく
for (int i = 2; i <= n; i ++) f[i] = f[i - 1] + f[i - 2]; //配列f[k]に計算結果を記録していく

　配列の最後にあるf[n]が求めるものとなる。ループ文中にあるf[i - 1]とf[i - 2]はすでに計算済みなので、再帰関数の時のような無駄がない。

練習問題

　最後にAtCoder(競技プログラミングサイト)にある動的計画法の過去問を貼っておくので、ご自身で実際に解いてみてほしい。

ABC040-C-柱柱柱柱柱
 Educational DP Contest-A-Frog1

　私もAtCoderをやっているのでぜひ一緒に精進しましょう〜。わからない点などあればTwitterでもいいので気軽に聞いてください。

おわり

　タイトルにもあるようにこれは初級編。今回扱った配列は１次元だったが、多次元配列を用いる動的計画法がわんさかある。まだまだ奥が深いのである。それでは、私のアルゴリズム力と実装力が上がった際に書くであろう中級編でお会いしましょう( ^_^)/~~~