The Fibonacci Numbers Algorithm with Tabulation

Simple recursion

Following is the simple implementation of the Fibonacci numbers algorithm. We covered this in one of the lessons from the first chapter. Please feel free to look at it before we continue to the bottom-up solution.

Bottom-up dynamic programming

Notice how we started from Fib(6) and went on to break it into Fib(5) and Fib(4). We saw that these had not been evaluated so we broke them further until we hit the base case. Now let’s look at an alternate approach, where we start from the base case, i.e., Fib(0) and Fib(1), and then build-up to the solution. We will keep storing all the subproblems along the way.

So, the plan is to start from Fib(0) and evaluate every Fibonacci number between 0 and n giving ...