Dynamic Programming is this topic that scares the crap out of everyone (myself included). This was one of those topics that took me a super long time to think about before it clicked. But I think I figured it out! My simple way of remembering Dynamic Programming is to think of iteration with memoization.
If those two things don’t mean anything to you, read on, otherwise, let’s recap with the previous Daily Problem as a warmup…
This article is part of the Data Structures and Algorithms Series following the course The Analysis of Algorithms. If you missed the previous article, check that out first as well as a copy of The Algorithm Design Manual.
Answers to the previous Daily Problem
Multisets are allowed to have repeated elements. A multiset of
_n_items may thus have fewer than_n!_distinct permutations. For example,{1,1,2,2}has only six different permutations:{1, 1, 2, 2}, {1, 2, 1, 2}, {1, 2, 2, 1}, {2, 1, 1, 2}, {2, 1, 2, 1}, and {2,2,1,1}. Design and implement an efficient algorithm for constructing all permutations of a multiset.
This question is basically asking “give me all of the shapes of these items”. Each permutation is a shape, or arrangement, of the 4 components, 2 of which are similar.
One approach would be to leverage backtracking, trying to figure out from those end results how do you get to the result with _n-1_ values left. This is a call back to our previous articles to re-assert your knowledge of backtracking algorithms. I will offer an alternative approach below:
Another naive approach is to make an _n^2_ loop between the number of possibilities and the number of slots and just insert each item into each slot. So 1 goes to first slot, then second slot, then third…then the second one goes into the first slot, then second slot… and you build out the possibilities by filling in the remaining options.
The problem is that doing the example above would arrive at duplicates (inserting the first 1 into the 4 slots yields the same shape of numbers as would if you inserted the second 1 into the 4 slots). So how do we eliminate these possibilities?
Caching. As we’ll see in this article, when we cache previous results, we can throw out unnecessary moves like constructing an unnecessary permutation. Once we’ve inserted the four options for the first 1, we don’t ever have to calculate them again for any other 1s because they yield the same output. Same with the 2s. So in the multiset example above, there are 24 different arrangements, duplicated twice (once for the 1 and once for the 2). In other words, we have 6x2x2 = 24, or 6 permutations that are duplicated once for 1 (x2) and once again for 2 (x2).
If that doesn’t make sense to you, check out how we handle generalized recurrence relations below.
Dynamic Programming = Recursion + Memoization
Functions that recurse call themselves. Memoization is just storing previously-computed results. Honestly, the best way to think about this is with a classic example, the Fibonacci Sequence:
const fibonacci = (n) => {
if (n === 1) return 0;
if (n === 2) return 1;
return fibonacci(n - 1) + fibonacci(n - 2);
}
All this algorithm says is
To get the number you’re looking for, add up the two previous numbers in the sequence
The first few numbers of Fibonacci are 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55. Simple, right? What’s the 24th number of Fibonacci? Oof! Yeah, this one gets rough pretty quick (in fact, it is exponentially bad!)
So we’ve got the recursive part in this function, but we’re missing the memoization. If we add in memoization, this problem becomes virtually linear in time, with the tradeoff of an array to store previous results:
const fibonacciCached = (n, cache = [0, 1]) => {
if (n === 1) return 0;
if (n === 2) return 1;
if (!cache[n]) cache[n] = fibonacciCached(n - 1) + fibonacciCached(n - 2);
return cache[n];
}
Literally one extra line to cache the result. The first solution will heat up your laptop if you find the 45th Fibonacci number from how hard it will be working. The latter will run extremely fast. All we did was make sure that if we’ve found this number before, we look it up in an array (constant-time lookup) as opposed to computing it all over again.
Simple, right? Well, not exactly.
For starters, this only works if you truly refer to the things you’ve computed. It works great here because we always refer to all of the numbers computed (since it’s always referring to lower numbers). But what about backtracking a path or with depth-first search? You may not always revisit everything there, in which case you’ve stored things unnecessarily.
Recursion also makes things painful. Recursion really eats up stack space. If we can cache with primitives and not recurse, that’s even better. With Fibonacci, it’s pretty easy:
const fibonacciArr = (n, cache = [0, 1]) => {
for (i = 2; i <= n; i++) cache[i] = cache[i - 1] + cache[i - 2];
return cache[n];
}
Brilliant! The shortest and the fastest solution yet with O(n) time and space! Now, to get really weird, we have to remember one thing that you probably noticed as you were counting Fibonacci: you only ever looked back two numbers when finding the next. Could our computer do that and only have to store 2 numbers as opposed to n? You bet!
const fibonacci2 = (n) => {
let first = 0, second = 1, next;
if (n <= 1) return 1;
for (let i = 2; i < n; i++) {
next = first + second;
first = second;
second = next;
}
return first + second;
}
A couple of more lines, but we all we’re doing is computing the next number by adding the two previous numbers (like we first specified in our definition of Fibonacci). To save space, we overwrite the variables and keep chugging along. The solution still runs in O(n) time but the space is now constant (the two recorded numbers plus the pointer to our upcoming to-be-computed number).
One final thing I’ll say about these last two examples: you may have noticed we traded in the full caching solution for less space. If constant space and linear time is fine with you (which it probably is) then stick with this.
However, if you plan to call a function over, and over, and over again, permanently storing a singleton of the cached values, it might be better to call something like fibonacciCached since you can always check if someone else has done this work before. The storage space is linear while the lookup time is constant for all but the uncharted territory. If you expect to visit previous values often, consider this alternative.
The basics are just scratching the surface
We’ve now introduced the fundamental aspects of Dynamic Programming with a few examples and variations. Read over the code a few times to let it sink in (trust me, it took a really long time for me to see this). We’ve got 2 more parts of this chapter to cover, so in the meantime, take a look at the Daily Problem and we’ll see you soon!
Onto the next Daily Problem
Suppose you are given three strings of characters:
X,Y, andZ, where|X| = n,|Y| = m, and|Z| = n + m.Zis said to be a shuffle ofXandYiffZcan be formed by interleaving the characters fromXandYin a way that maintains the left-to-right ordering of the characters from each string. (a) Show thatcchocohilaptesis a shuffle ofchocolateandchips, butchocochilatspeis not. (b) Give an efficient dynamic-programming algorithm that determines whetherZis a shuffle ofXandY. Hint: the values of the dynamic programming matrix you construct should beBoolean, not numeric.
More problems to practice on
Now that homework 5 is out, here are a few problems that are relevant to the dynamic programming we’ve discussed so far:
- Problem 8-3.
- Problem 8-7.
Think on this and we’ll check it out in the next few days as we explore more examples of Dynamic Programming.
Get the FREE UI crash course
Sign up for our newsletter and receive a free UI crash course to help you build beautiful applications without needing a design background. Just enter your email below and you'll get a download link instantly.