{ Dynamic Programming. }
Objectives
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
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.
Fibonacci
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!
Memoization vs. Tabulation
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.
Fibonacci With Dynamic Programming
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.
Other Dynamic Programming Problems
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
