目標

動的計画法の基本的なアイディアを理解する。

フィボナッチ数列

次のように定義されます。

$fib(n) = \left \{ \begin{array}{} 1 && (n = 0) \\ 1 && (n = 1) \\ fib(n-1) + fib(n-2) && (otherwise) \\ \end{array} \right.$

いかにも再帰関数で書けそうです。

素朴な再帰関数による実装

nを入力として与えると、フィボナッチ数列の第n項を出力するようなプログラムを書いてみます。

まずは何も考えずに書いてみます。

#include<iostream>
using namespace std;

int fib(int n) {
  if (n == 0 || n == 1) return 1;
  return fib(n-2) + fib(n-1);
}

int main() {
  int n;

  cin >> n;
  cout << fib(n) << endl;

  return 0;
}

漸化式そのままで非常に簡単なのですが、考えてみればこの方法は無駄が多いです。なぜなら、同じ式をなんども呼び出して同じ計算をすることになるからです。例えば、fib(4)を呼ぶと、fib(2) + fib(3)が呼ばれ、さらにfib(3)はfib(2)を呼び出します。１回ごとに２つの関数を呼び出しているので、計算量は $O(2^ N)$ になります。

このような無駄を排除するアイディアがメモ化です。

メモ化再帰を使った実装

メモ化というのは、要するに一度計算した値を記録しておき、再利用するということです。

#include<iostream>
using namespace std;

int F[50];

int fib(int n) {
  if (n == 0 || n == 1) {
    F[n] = 1;
    return 1;
  }
  
  if (F[n] != -1) return F[n];  // 計算ずみ

  F[n] = fib(n-2) + fib(n-1);
  return F[n];
}

int main() {
  int n;

  // 初期化
  for (unsigned long i = 0; i < sizeof(F) / sizeof(int); i++) F[i] = -1;

  cin >> n;
  cout << fib(n) << endl;

  return 0;
}

F[n]に計算済みの値を記録しておきます。すでに計算したかどうかを判定するためにF[n]の初期値を-1にしてあります（数列で出てこない値ならば何でも良い）。

このような手法をメモ化再帰と言います。動的計画法の１つのアプローチです。計算量は $O(N)$ ですね。大幅に効率が良くなりました。

次のように、メモ化再帰とは異なり、ループを使ってボトムアップで解くこともできます。こっちの方が直感的ですね。

#include<iostream>
using namespace std;

int main() {
  int n, fib[50];

  cin >> n;

  fib[0] = 1;
  fib[1] = 1;
  for (int i = 2; i <= n; i++) {
    fib[i] = fib[i-2] + fib[i-1];
  }
  
  cout << fib[n] << endl;

  return 0;
}