Fibonacci with Memo

Fibonacci with Memo

Medium PHP PHP Functions 38 views
Explanation Complexity

Problem Statement

Compute fib(n) with memoization (fib(0)=0, fib(1)=1).

Input Format

One integer n.

Output Format

One integer.

Example

10
55

Constraints

0

Input / Output Format

Input Format
One integer n.
Output Format
One integer.
Constraints
0

Examples

Input:
10
Output:
55

Example Solution (Public)

PHP 
<?php
$inputText=trim(stream_get_contents(STDIN));
if($inputText==='') exit;
$n=intval($inputText);
$memo=[0=>0,1=>1];
function fib($n,&$memo){
  if(isset($memo[$n])) return $memo[$n];
  $memo[$n]=fib($n-1,$memo)+fib($n-2,$memo);
  return $memo[$n];
}
echo fib($n,$memo);
?>

Official Solution Code

<?php
$inputText=trim(stream_get_contents(STDIN));
if($inputText==='') exit;
$n=intval($inputText);
$memo=[0=>0,1=>1];
function fib($n,&$memo){
  if(isset($memo[$n])) return $memo[$n];
  $memo[$n]=fib($n-1,$memo)+fib($n-2,$memo);
  return $memo[$n];
}
echo fib($n,$memo);
?>
Please login to submit solutions.
Editor
Output

                                        

                                    

                                    

                                        

                                                                                    
Please login to submit solutions.