Bottom-Up vs Top-Down Algorithms | Skilled.dev
Learn

Bottom-Up vs Top-Down

Course launching November 17, 2020

Follow me on YouTube for free coding interview videos.

Users who sign up for the email list will receive an exclusive 75% discount at launch.

Your subscription could not be saved. Please try again.
Your subscription was successful! 🤓
Loading...

There are two ways to approach dynamic programming problems, and that is a bottom-up algorithm and a top-down algorithm. 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-dowm or bottom-up equally.

Bottom-Up Approach

The bottom-up takes the simplest value(s) and builds on top of it to reach the solution. This is often the most intuitive way for people to solve problems when they are newer to programming.

Calculating 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 our way to the solution.

function fibonacci(n) {
  let first = 0;
  let second = 1;

  for (let i = 2; i < n; i++) {
    let temp = first + second;
    first = second;
    second = temp;
  }

  return first + second;
}

Top-Down Approach

For the top-down approach, we start by considering the final solution and express 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 values until it reaches the base case. Once we reach the base case, the values are returned through the functions calls, and we combine the answers to build the final solution.

Since the 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 number before n, we can then use their results to calculate fibonacci(n).

function fibonacci(n) {
  // Base case
  if (n < 2) {
     return n
  }

  // Sum the two previous numbers to get the current value
  return fibonacci(n - 1) + fibonacci(n - 2)
}

Optimization

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

Prev
Memoization
Next
Dynamic Programming
Loading...

Table of Contents