Now that we have covered the basics of Dynamic Programming , let us look at how to actually approach the Fibonacci number problem.

We can calculate the fibonacci number as follows:

fib(0) = 0
fib(1) = 1
fib(n) = fib(n-1) + fib(n-2) where n>0

We will discuss the following 3 approaches:

1. Basic recursive
2. Top-down DP with Memoization
3. Bottom-up DP with tabulation

1. Basic Recursive solution

Here's how the pseudocode looks like

def fib(n):
    if n < 2 return n
    if n > 1 return fib(n-1) + fib(n-2)

Time complexity = exponential O(2^n) as we are making two recursive calls in the same function. Space complexity = O(n) to store the recursion stack.

2. Top-down DP with memoization

As we can see above, fib(2) is calculated twice, fib(1) is calculated thrice etc which adds unnecessary overhead to our problem.

Let us now use an array to store the already solved subproblems.

Each time we need to solve a sub-problem, we check if the value is already stored in the array. If yes, we return the value from array. If the value isn't present in the array, we solve the subproblem and update the array with the calculated value.

Here's the pseudocode:

dp = array of size n+1

def fib(n):
   if n < 2 return n
   if dp[n] == 0:
       dp[n] = fib(n-1) + fib(n-2)
   return dp[n]

3. Bottom up DP with tabulation

Here we avoid recursion and start solving the subproblems first and slowly build up the solution for the main problem.

In case of fibonacci, since we have the base case and the formula for fib(n) we will solve the problem for every value till n.

Here's the pseudocode:

def fib(n):
    dp = array of size n+1
    dp[0] = 0
    dp[1] = 1
    for i in range 2..n:
        dp[n] = dp[n-1] + dp[n-2]
    return dp[n]

This solution has time and space complexity of O(n).

Now that we have the pseudocode for all approaches, try to solve this problem on LeetCode

Do attempt to solve these on your own before looking at the solutions here

Share your code in comments.

You can also comment for any clarifications/feedback.

Follow me for more content to crack your coding interviews. I will be covering all 5 patterns of Dynamic programming questions in Aug so stay tuned !

Happy coding. Cheers !