Categories
Interview Interview questions

How to Fibonacci Bottom-Up Memoization PHP ? Dynamic Programming

This function runs in O(n) time

<?php
function fibonacci(int $n) {
    if ($n == 0) {
        return 0; 
        
    }    else if ($n == 1) {
        return 1;
    }
    
    $memo = array_fill(0, $n, 0);
    $memo[0] = 0;
    $memo[1] = 1;
    
    for ($i = 2; $i < $n; $i++) {
        
        $memo[$i] = $memo[$i - 1] + $memo[$i - 2] ;   
        echo    "memo[$i] ($memo[$i]) = memo[$i - 1] + memo[$i - 2] \n\r";   
        
    }
    return $memo[$n - 1] + $memo[$n - 2];
}

OR

function fibonacci(int $n) {
    if ($n == 0) {
        return 0; 
        
    }    else if ($n == 1) {
        return 1;
    }
    
    $memo = array_fill(0, $n, 0);
    $a = 0;
    $b = 1;
    
    for ($i = 2; $i < $n; $i++) {
        
       $c = $a + $b ;   
        $a = $b;
        $b = $c;
        echo    "c ($c) = a ($a) + b ($b)  \n\r";   
        
    }
    return $a + $b;

Leave a Reply