【PHP】メモ化再帰

同じ計算を2度以上しないで、メモするという話

$arr = array();
$arr = array_pad($arr, 999, -1);

function memo01($n){

    global $arr;

    if($n == 0) return 0;
    if($n == 1) return 1;

    if($arr[$n] != 0) {
        return $arr[$n];
    }

    $arr[$n] = memo01($n - 2) + memo01($n - 1);
    //echo $n." = ".$arr[$n]."<br/>";
    return $arr[$n];

}

echo memo01(100);