top down approach
//===========Top_down implementation (just recursive)
fib(int n){
if(n<2){
return n;
return fib(n-1) + fib(n-2);
}
}
//===========Top_down implementation (recursive + memoization)
fib(int n){
if(n<2){
return n;
if(cache[n] is defined)
return cache[n];
return cache[n]=fib(n-1) + fib(n-2);
}
}
//===========Top_down implementation(avoid recursion , only tabulation)
fib(int n){
int cache[] = new int [n+1];
//base case;
cache[0]=1;
cache[1]=1;
for(int i=2; i<=n; i++){
cache[1] = cache[i-1] +cache[i -2];
}
return cache[n];
}