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]; }
