DPとは何か フィボナッチで

Programming

主に漸化式で与えられる問題を解くのに使われる動的計画法(DP)。

DPとメモ化再帰の定義を、フィボナッチ数列を計算するプログラムを例にして考える。

/* 「フィボナッチ 再帰バージョン」
 * フィボナッチ数列を漸化式の通りに実装したもの
 * この計算ではO(1.618^N)つまり指数オーダーの時間がかかる
 */

#include <stdio.h>

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

int main(int argc, char **argv)
{
    printf("%d\n", fib(10));
    return 0;
}

/* 「フィボナッチ メモ化再帰バージョン」
 * 計算結果を配列に保存するようにした再帰
 * この計算では線形時間でできる
 */

#include <stdio.h>

int fib_memo[10000] = {0};
int fib(int n) {
    if(n==0)return 0;
    if(n==1)return 1;
    if(fib_memo[n] != 0) {
        return fib_memo[n];
    }
    return fib_memo[n] = fib(n-1)+fib(n-2);
}

int main(int argc, char **argv)
{
    printf("%d\n", fib(46));
    return 0;
}

/* 「フィボナッチ 動的計画法バージョン」
 * メモ化再帰とは計算の方向が逆(nが増加する方向)になる。
 * 再帰が無くなる。
 * この計算でも線形時間でできる
 */

#include <stdio.h>

int fib_memo[10000];
int fib(int n) {
    int i;
    fib_memo[0] = 0;
    fib_memo[1] = 1;
    for(i = 2; i <= n; ++i) {
        fib_memo[i] = fib_memo[i-1] + fib_memo[i-2];
    }
    return fib_memo[n];
}

int main(int argc, char **argv)
{
    printf("%d\n", fib(46));
    return 0;
}

まとめ

  • 同じ計算が何度も行われる再帰がある
  • その関数を配列にメモして、計算量を削減するのが「メモ化再帰(メモ化DFS)」
  • メモ化再帰は、再帰なので、
    • 目的となる関数が呼ばれる→それが必要とする値を計算→目的の値が出る
  • 動的計画法は計算の順番を変えたもの
    • 前もって計算の依存関係がわかっているときに行う。
    • メモ化再帰が目的値から依存してる値に向かうのに対して、DPは必要な値から目的の値、という計算方向をもつものを指す
  • メモ化再帰と動的計画法は、だいたいどちらでも解ける感じだけど、微妙に違うかも