※Qiitaに”動的計画法とメモ化”を説明する記事を書きましたので，こちらにも記載したいと思います．内容は全く同じです(>_<) qiita.com

動的計画法とメモ化

動的計画法（Dynamic Programming）とメモ化（Memorization）は，競技プログラミングなんかでよく使われるアルゴリズムの一緒です．両者とも計算結果を保存し再利用することで，重複した計算による時間ロスを防ぐものです．

例を示しながら説明したいと思います．

動的計画法 or メモ化を使う動機

まず，フィボナッチ数列とは

n 番目のフィボナッチ数を Fn で表すと、Fn は再帰的に F0 = 0, F1 = 1, F(n + 2) = Fn + (Fn + 1) (n ≧ 0)

で定義される数列です．（Wikipediaより）

標準入力から入力される数字を n とし n 番目（0番目スタート）のフィボナッチ数を求めたい場合どう実装するでしょうか．

（色々な方法はあると思いますが）数学的に一般項を求めようとせず，定義をそのまま使うと，こんな感じの再帰的な処理が書けると思います．

<?php
fscanf(STDIN, "%d", $n);
echo fib($n) . "\n";
function fib($n) {
    if ($n == 0) return 0;
    if ($n == 1) return 1;
    return fib($n - 1) + fib($n - 2);
}

しかし，これだと尋常じゃない時間がかかります． n=4でもこれだけ再帰的にfib関数が呼ばれるんです↓

fib(4) = fib(3) + fib(2)
 = (fib(2) + fib(1)) + (fib(1) + fib(0))

この時間を短縮しくてれるのが動的計画法 or メモ化です！使いたくなりませんか？w では，実際にコードへ適用していきます．

メモ化でフィボナッチ数を求める

ポイントは$memoListという配列に計算結果を保存しておき，余計な計算を減らすことです． n 番目から計算するトップダウンなイメージです．コードにするとこんな感じです．

<?php
fscanf(STDIN, "%d", $n);
echo fib($n) . "\n";

$memoList;

function fib($n) {
    global $memoList;
    if (isset($memoList[$n])) return $memoList[$n]; // 保存済みならその結果を使う
    if ($n == 0) return 0;
    if ($n == 1) return 1;
    $memoList[$n] = fib($n - 1) + fib($n - 2); // 新たに計算した結果を保存する
    return fib($n - 1) + fib($n - 2);
}

動的計画法でフィボナッチ数を求める

ポイントは$dpという配列で，計算結果を保存するという点ではメモ化と一緒です．ただ，こちらはメモ化とは逆向きに，0番目から計算するボトムアップなイメージです．だから，関数は一度呼ぶだけです．

<?php
fscanf(STDIN, "%d", $n);
echo fib($n) . "\n";

function fib($n) {
    $dp[0] = 0;
    $dp[1] = 1;

    for ($i = 2; $i <= $n; $i++) { // ひたすら計算し，結果を配列に保存していく
        $dp[$i] = $dp[$i - 1] + $dp[$i - 2];
    }

    return $dp[$n];
}