Bottom-Up vs. Top-Down

There are two ways to approach dynamic programming problems, and that is bottom-up algorithms and top-down algorithms. The easiest way to remember them is that bottom-up is iterative and top-down is recursive.

The bottom-up approach is often preferred because you don't have the risk of a stack overflow from recursion or incur the space complexity from the call stack. However, if your language implements tail-call optimization, then the recursive approach uses constant space and its downsides no longer matter, and you can use either top-down or bottom-up equally.

Bottom-Up Approach

Bottom-up takes the simplest/smallest value(s) and builds up from these to reach the solution. This is often the most intuitive way for people to solve problems when they are newer to programming.

To calculate a large fibonacci(n), we start at the bottom which is 0 and 1 for the first two items in the sequence. Then we repeatedly sum them together and build up to the solution. Each iteration of the loop is solving a subproblem to calculate a given Fibonacci number.

Top-Down Approach

For the top-down approach, we start by considering the final solution and describe it as a combination of the results of a series of subproblems. This is our recursive approach.

We start at the top (final state we want) and express it as a recursive function. The recursive function then calls itself with smaller input values until it reaches the base case. Once we reach the base case, the results are returned through the functions calls, and we combine the answers to build the final solution.

Since a Fibonacci number is just the sum of the two Fibonacci numbers before it, if we solve this as a combination of subproblems with the same logic for every Fibonacci number, we can then use their results to calculate any fibonacci(n).

Optimization

In dynamic programming, we use memoization to store the result of a subproblem so we don't repeat work when they overlap. We incur additional space complexity to store the result of each step so we can look up a result later without performing the computation again. Memoization can be used for both bottom-up and top-down.