This lesson's interactive features are locked, please to keep using them

Fast Fibonacci – Tabulation

We actually have a few different dynamic programming techniques to choose from, even with a problem as simple as the Fibonacci sequence.

Memoization is considered a "top-down" optimization. It's top-down because we start with the whole problem and then move down into the subproblems (via recursive function calls).

Bottom-Up Dynamic Programming

What if we took the opposite approach, starting with the subproblems and working our way up to the overall problem? That would be a "bottom-up" technique, and there's a good way of doing that for the Fibonacci numbers, called tabulation.

Tabulation involves solving all the subproblems first, then assembling their solutions into the final solution.

Assignment

Just like before, we need to complete an alternative fast version of the fibonacci function so that we have an answer key for the Mappy interview process.

Update fibonacci to be even faster using tabulation.

Create a list with n + 1 items initialized to 0. Each item in the list, at index i, will represent the result of fibonacci(i).
Set the first two values in the list to 0 and 1. Be careful, though: if n is 0, the list will have only one item. Handle that case accordingly.
For each number between 2 and n, inclusive, set the list item at that index to the sum of the previous two values.
Return the list item at index n.