Skip to content

Instantly share code, notes, and snippets.

@CMCDragonkai
Created October 27, 2014 09:07
Show Gist options
  • Save CMCDragonkai/e5cb9f75547a3c585d70 to your computer and use it in GitHub Desktop.
Save CMCDragonkai/e5cb9f75547a3c585d70 to your computer and use it in GitHub Desktop.
PHP: Dynamic Fibonnaci O(n)
<?php
// O(n) time complexity with constant space complexity
function fibonacci_dynamic($n){
if($n == 0){
return 0;
}elseif($n == 1 OR $n == 2){
return 1;
}
$fib[0] = 0;
$fib[1] = 1;
for($i=2; $i<=$n; $i++){
$current_fib = $fib[0] + $fib[1];
$fib[0] = $fib[1];
$fib[1] = $current_fib;
}
return $fib[1];
}
var_dump(fibonacci_dynamic(10));
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment