Fibonacci

In Recursion, we calculate the same value many times, which leads to exponential time complexity O(2n). With Dynamic Programming, we store the results (memoization) and reduce the time to O(n).
similar qeustion n-th-tribonacci
playlist DP Playlist

Recursion Dynamic Programming
Repeated calls Memoization
O(2n) O(n)
Simple but inefficient Efficient and scalable
Fibonacci

C++ Code:

vector<int> memo(n+1, -1);

int fib(int n) {
      // base case
    if(n <= 1) return n;
    // memo 
    if(memo[n] != -1) return memo[n];
    // transition
    return memo[n] = fib(n-1) + fib(n-2);
}

Contact Me

GitHub GitHub LinkedIn LinkedIn
Send me an Email