March 27, 2020

Dynamic programming is a fancy name for something you probably do already: efficiently solving a big problem by breaking it down into smaller problems and reusing the solutions to the smaller problems to avoid solving them more than once. In this tutorial, you will learn the fundamentals of the two approaches to dynamic programming: memoization and tabulation.

This article is part of a series on Big O notation. If you’re just joining us, you may want to read the previous article, Big O Recursive Space Complexity, or start at the beginning with What is Big O Notation?.

- Dynamic programming helps us optimize solutions to problems by caching values for future use
- Dynamic programming helps us improve the runtimes of recursive algorithms

There are two criteria for a dynamic programming approach to problem solving:

- Optimal substructure
- Overlapping subproblems

What is *optimal substructure*?

The solution to a larger problem can be found by combining the returned values of its smaller problems.

Like recursion and proof by induction, we recognize a pattern and apply the same approach to solving the parts as we would the whole.

What are *overlapping subproblems*?

The solution to a larger problem recognizes redundancy in the smaller problems and *caches* those solutions for later recall rather than repeatedly solving the same problem, making the algorithm much more efficient.

Both of these concepts will click when we refactor our naive sum of Fibonacci sequence algorithm.

☝️ This might sound a lot like divide and conquer, but divide and conquer algorithms, such as merge sort and quick sort, don’t solve overlapping subproblems. They continually divide a problem into smaller, yet new, problems, then recombine the smaller solutions into a solution to the larger problem.

There are two approaches for implementing a dynamic programming solution:

- Top-down
- Bottom-up

The top-down approach is generally recursive (but less efficient) and more intuitive to implement as it is often a matter of recognizing the pattern in an algorithm and refactoring it as a dynamic programming solution.

The bottom-up approach is generally iterative (and more efficient), but less intuitive and requires us to solve (and know!) the smaller problems first then use the combined values of the smaller problems for the larger solution.

We refer to top-down solutions as *memoization* and bottom-up as *tabulation*.

We’ll look at the reason for these terms below.

But first, a quick refresher.

We’ll revisit our naive recursive sum of Fibonacci sequence for this tutorial. If you’re just joining us, you may want to first read Big O Recursive Time Complexity.

The sum of the Fibonacci sequence is a contrived example, but it is useful (and concise) in illustrating the difference between memoization and tabulation and how to refactor a recursive function for improved time and space complexity.

Here’s our naive implementation of the sum of the Fibonacci sequence.

```
const fibonaive = n => {
if (n == 0 || n == 1) {
return n;
}
return fibonaive(n - 1) + fibonaive(n - 2);
};
```

Why is it *naive*?

Because the runtime is *really* bad.

It’s O(2^n).

(Actually, it’s O(1.6^n), but who’s counting?)

Take a look at this diagram of our recursive call branches.

Why is this algorithm inefficient?

Overlapping subproblems!

We solve the same problems repeatedly in our branches.

How many times do we solve `f(0)`

?

How many times do we solve `f(1)`

?

How many times do we solve `f(2)`

?

How many times do we solve `f(3)`

?

The answer to all of the above is: too many!

Memoization is the top-down approach to solving a problem with dynamic programming.

It’s called memoization because we will create a *memo*, or a “note to self”, for the values returned from solving each problem.

Then, when we encounter the same problem again, we simply check the memo, and, rather than solving the problem a second (or third or fourth) time, we retrieve the solution from our memo.

Here’s our Fibonacci sequence, memoized:

```
const fibDown = (n, memo=[]) => {
if (n == 0 || n == 1) {
return n;
}
if (memo[n] == undefined) {
memo[n] = fibDown(n - 1, memo) + fibDown(n - 2, memo);
}
return memo[n];
}
```

Where have we seen this, or something like it, before?

🤔

It’s very similar to our naive implementation.

But!

We now pass our function a `memo`

argument and initialize it as an array.

Each time we recursively call `fibDown()`

, we pass it the `memo`

array.

If the value of `memo[n]`

is undefined, meaning there’s no value stored in that index yet, we assign that value the returned values of `fibDown(n - 1, memo) + fibDown(n - 2, memo)`

.

What’s the time complexity?

O(n).

Why?

Because we don’t solve the *overlapping subproblems*.

This is a big improvement over the naive implementation.

What’s the space complexity?

Also O(n).

With bottom-up, or *tabulation*, we start with the smallest problems and use the returned values to calculate larger values.

We can think of it as entering values in a table, or spreadsheet, and then applying a formula to those values.

Here’s our Fibonacci sequence, *tabulated*:

```
const fibottomUp = n => {
if (n === 0) {
return 0;
}
let x = 0;
let y = 1;
for (let i = 2; i < n; i++) {
let tmp = x + y;
x = y;
y = tmp;
}
return x + y;
}
```

Where have we seen this, or something like it, before?

🤔

This solution is very similar to a swap algorithm.

We declare three local variables, `x`

, `y`

and `tmp`

and then juggle the values.

What is the Big O of `fibottomUp()`

?

Like memoization above, the time complexity is also O(n).

Why?

We are using a `for`

loop to iterate over the value of `n`

.

But the space complexity is O(1).

Why?

No recursion.

We are only pushing one call to the stack.

Which is better? Memoizaiton or tabulation?

If we don’t need to solve *all* the problems and are just looking for the optimal solution, memoization is better.

If we do need to solve all the problems, that means we are going to make a lot of recursive calls, and tabulation is better.

The caveat is that memoization is generally more intuitive to implement especially when we don’t know the solution to subproblems, whereas tabulation requires us to know the solutions, or bottom, in advance, in order to build our way up.

In this tutorial, you learned the fundamentals of the two approaches to dynamic programming: memoization and tabulation. Stay tuned for the next articles in this series: Big O factorial time complexity and NP-complete problems.

Want to level up your problem solving skills? I write a weekly newsletter about programming, problem solving and lifelong learning. Join now