[C#] フィボナッチ数を動的計画法とメモ化で求める [VB]

動的計画法(Dynamic Programming)とは

動的計画法 – Wikipedia

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

簡単に言うと、一度計算した結果を保持しておいて再び利用するときは計算を省略することで処理の効率化を図る方法です。

例えば フィボナッチ数 を求める処理を考えます。

フィボナッチ数

F(0) = 0,
F(1) = 1,
F(n + 2) = F(n) + F(n + 1) (n ≧ 0)

フィボナッチ数を求める式は上記の通りです。これを単純に再起処理で求めると以下のような関数になります。

  static int Fib(int n)
  {
      var f = 0;
      switch (n)
      {
          case 0:
          case 1:
              f = n;
              break;
          default:
              f = Fib(n - 2) + Fib(n - 1);
              break;
      }
      return f;
  }

これでも動作するのですが、再起処理の中で同じ処理が何度も呼ばれます。

例えば n=3 の時、Fib(1) と Fib(2) が呼ばれます。そして n=2 の時、つまり Fib(2) の中では Fib(1) が呼ばれることになります。このように n が大きくなると、同じ Fib(X) が何度も何度も呼ばれるようになります。

何度も同じ処理を呼ぶのは無駄なので、一度計算した結果をメモしておく方法が考えられます。

メモ化

メモ化 – Wikipedia

メモ化（英: Memoization）とは、プログラムの高速化のための最適化技法の一種であり、サブルーチン呼び出しの結果を後で再利用するために保持し、そのサブルーチン（関数）の呼び出し毎の再計算を防ぐ手法である。メモ化は構文解析などでも使われる（必ずしも高速化のためだけとは限らない）。キャッシュはより広範な用語であり、メモ化はキャッシュの限定的な形態を指す用語である。

メモ化も動的計画法の一種らしいです。

一度計算した結果をメモしておき、再度呼ばれたときはその値を返すようにします。つまり必要に応じてメモしておくということになります。

static Dictionary<int, int> Memo = new Dictionary<int, int>();

static int Fib(int n)
{
    if (Memo.ContainsKey(n)) return Memo[n];

    var f = 0;
    switch (n)
    {
        case 0:
        case 1:
            f = n;
            break;
        default:
            f = Fib(n - 2) + Fib(n - 1);
            break;
    }
    Memo[n] = f;
    return f;
}

単純ですね。メモを辞書で管理し、Fib(n) 呼び出し時にメモに値があればそれを返します。なければ計算してメモに追加しておきます。

これでかなり処理時間が短縮されます。例えば Fib(40) くらいの大きさを計算するとかなり顕著に差がわかると思います。

動的計画法(ボトムアップ方式)

必要に応じて計算結果をメモするのではなく、先に部分問題を解いていく方法もあります。

つまり Fib(0) -> Fib(1) … Fib(n) の順に計算する方法です。この方法では計算量は変わりませんが複雑な再起処理がなくなり、ループで処理できるようになります。

F(0) = 0,
F(1) = 1,
F(n + 2) = F(n) + F(n + 1) (n ≧ 0)

フィボナッチ数の漸化式は上記の通りです。漸化式が求まればそれを使ってすっきりと以下のように書けます。

static Dictionary<int, int> Memo = new Dictionary<int, int>();

static int Fib(int n)
{
    Memo[0] = 0;
    Memo[1] = 1;
    for (int i = 2; i <= n; i++)
    {
        Memo[i] = Memo[i - 1] + Memo[i - 2];
    }
    return Memo[n];
}

Fib(n) の計算には漸化式をみると Fib(0)..Fib(n-1) の計算結果が必要なので、それを順番に計算していきます。結果 Fib(n) が求まるという寸法です。

VB.NET での実装

Public Memo As Dictionary(Of Integer, Integer) = New Dictionary(Of Integer, Integer)()

Function Fib(n As Integer) As Integer
    Memo(0) = 0
    Memo(1) = 1
    For index = 2 To n
        Memo(index) = Memo(index - 1) + Memo(index - 2)
    Next
    Return Memo(n)
End Function

以上。