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

Bottom-Up vs Top-Down

Course launching August 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! 🤓

SHOULD THIS BE PART OF THE DYNAMIC PROGRAMMING ARTICLE?

There are two ways to approach dynamic programming problems, and that is a top-down algorithm and a bottom-up algorithm. The easiest way to remember 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 use the memory for the call stack.

Bottom-Up Approach

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

For example, if we want to calcualte n!, we start at the bottom. We know 1! = 1, 2! = 2 * 1, 3! = 3 * 2 * 1, and so on. So we start with the simplest case and build up from it. To fully code it out:

function factorial(number) {
  let factorial = 1;

  for (let i = 1; i <= number; i++) {
    factorial = factorial * i;
  }

  return factorial;
}

The bottom-up/iterative solution to the Fibonacci function works the same way. Calculating a large fib(n), we need the numbers before it. So for fib(1000) = fib(999) + fib(998) would require more work because we don't know where the two previous values are to start. However, we do know where the Fibonacci sequence starts with fib(0) = 1 and fib(1) = 1. By starting with these two values, we can build up from the bottom to calculate the Fibonacci number for any n.

function fibonacci(n) {
  if (n <= 2) {
    return 1;
  }

  let a = 1;
  let b = 1;

  for(let i = 3; i <= n; i++) {
    let c = a + b;
    a = b;
    b = c;
  }

  return b;
}

Top-Down Approach

For the top-down approach, we start by considering the complex case and think how it can be solved by combining the results of a series of subproblems. This is our recursive approach which means we need a base case and recursive case in our function.

So we start at the top (final state we want) and express it as a recursive function. The recrusive function then calls itself until it reaches the base case which builds our solution.

In dynamic programming, we always use memoization to store the result of a sub-problem so we don't repeat work when they overlap.

To calculate the factorial, we realize that to calculate any n!, we only need to find factorial(n) = n * factorial(n - 1). If we repeat this function for the numbers before n and combine their results, we will have then calculate n!.

function factorial(number) {
  if (number <= 1) {
    return 1;
  }

  return number * factorial(number - 1);
}

The top-down approach for calculating Fibonacci numbers follows the same logic. Since the Fibonacci number is just sum of the two Fibonacci numbers before it, if solve this subproblem with the same logic for each number before n, we can then use their results to calculate fibonacci(n).

function fibonacci(num) {
  // Base case
  if (num <= 1) {
     return num
  }

  // Sum the two previous numbers to get the current value
  return fibonacci(num - 1) + fibonacci(num - 2)
}
Prev
Memoization
Next
Backtracking

Table of Contents