×

By the end of this chapter you should be able to:

- Define dynamic programming
- Solve Fibonacci sequence using dynamic programming
- Solve the largest common subsequence problem

Dynamic programming is a useful problem solving technique that often helps to make your programs more efficient. The basic idea is that you solve smaller problems and *remember* the result of those smaller problems in case you encounter them again. By remember solutions to smaller problems, you can more quickly figure out the larger problem.

Let's take a look at an example.

The fibonacci sequence is a problem commonly taught when learning recursion. The sequence is defined by the following formulas:

fib(0) = 0 fib(1) = 1 fib(2) = 1 fib(n) = fib(n-1) + fib(n-2)

Therefore the beginning of the sequence would be:

0 1 1 2 3 5 8 13 21 34 55 89...

After `fib(2)`

, you can see that any number is simply the addition of the previous two numbers in the sequence.

To solve this problem, we can use recursion. The base cases are `fib(0)`

, `fib(1)`

, and `fib(2)`

. Otherwise, return `fib(n-1) + fib(n-2)`

function fib(n) { if (n <= 0) { return 0; } if (n <= 2) { return 1; } return fib(n - 1) + fib(n - 2); }

This implementation is easy to understand, but let's look at all of the stack frames that get created when you make a call to `fib(5)`

. If you are using the sources tab with the Chrome Dev Tools, you can set a break point inside the function and examine the call stack on the right hand side.

In this case, the stack will be growing downward and each line is a stack frame. We are taking a look at the stack after the first base case is returned.

fib(5), n = 5, line number 6 waiting on fib(n-1) fib(4), n = 4, line number 6 waiting on fib(n-1) fib(3), n = 3, line number 6 waiting on fib(n-1) fib(2), n = 2, line number 3, RETURN 1

So far, `fib(3)`

is waiting on `fib(2)`

and it will get its result, which is 1. Now, `fib(3)`

will get the result for `fib(1)`

which is also, 1. Here is our new stack snapshot:

fib(5), n = 5, line number 6 waiting on fib(n-1) fib(4), n = 4, line number 6 waiting on fib(n-1) fib(3), n = 3, line number 6, RETURNING 1 + 1

Now we can see, that the `fib(4)`

stack frame will be getting 2 for its invocation of `fib(3)`

, and the next step is to ask for `fib(2)`

. But wait! We already computed `fib(2)`

! Here is our next snapshot:

fib(5), n = 5, line number 6 waiting on fib(n-1) fib(4), n = 4, line number 6, RETURNING 2 + 1

Now `fib(5)`

will get back the result 3 for the invocation of `fib(4)`

, but next, it will compute `fib(3)`

, which we already did!

If you continue to look at the stack for larger values of n, the computations are very redundant and the program becomes extremely slow.

If you try to compute `fib(50)`

, it may already be too much for your computer to handle in a reasonable amount of time!

We mentioned earlier that dynamic programming is a technique for solving problems by breaking them down into smaller subsets of the same problem (using recursion). To solve problems using dynamic programming, there are two approaches that we can use, `memoization`

and `tabulation`

The idea of 'storing' the result of an expensive function (fib) is known as `memoization`

. Memoization is implemented by maintaining a lookup table of previous solved sub-problems. This approach is also known as "top down" since you solve the solve the "top" problem first (which typically recurses down to solve the sub-problems).

When you solve a dynamic programming problem using `tabulation`

you solve the by solving all related sub-problems first. This means that you must decide in which order to solve your sub-problems first, which adds another step, but gives you more flexibility than `memoization`

. This approach is traditionally known as a "bottom up" approach since the sub-problems are calculated first. You can read more about the differences here

So which one should you use? As with most of these questions, the answer is "it depends" - you can read more about when to use which one here or here.

**Problem**: The naive Fibonacci implementation recomputes two values of Fibonacci that we have already computed.

**Solution**: Use dynamic programming along with memoization to save values in a hash in order to not have to recompute values that have already been computed.

Below is the dynamic programming solution that uses `memoization`

(done with an object) to store the values of `fib(n)`

. If the values are needed again, they can be looked up using `savedFib`

without having to recompute them.

function fib(n, savedFib={}) { // base case if (n <= 0) { return 0; } if (n <= 2) { return 1; } // memoize if (savedFib[n - 1] === undefined) { savedFib[n - 1] = fib(n - 1, savedFib); } // memoize if (savedFib[n - 2] === undefined) { savedFib[n - 2] = fib(n - 2, savedFib); } return savedFib[n - 1] + savedFib[n - 2]; }

Here is a solution to the same Fibonnaci problem using `tabulation`

.

function fib(n){ // array declaration - notice that we figure out how many elements will be here before the calculations begin. This is the 'tabulation' approach so let's make a new array and fill it with 0s var arr = new Array(n+1).fill(0) // base case assignment arr[1] = 1; // calculating the fibonacci and storing the values for(var i = 2; i <= n; i++){ arr[i] = arr[i-1] + arr[i-2] } return arr[n] }

It's important to understand that both of these options can be used to solve dynamic programming problems so they are not mutually exclusive.

Dynamic programming can be used to solve more difficult problems as well with better time complexities. Here are some problems that can be solved with dynamic programming (first try a brute force solution and then move on to dynamic programming when solving these):

Here are some excellent resources for learning more about Dynamic Programming:

When you're ready, move on to Searching Algorithms