Dynamic Programming Overview

[00:00:00]
>> So because we're using so much memory when we're caching, we need to be careful about how a memoized function is going to be used. And we need to think about what types of inputs are gonna come in. For example, if you had a function that was taking in the XY coordinates of somebody's mouse cursor as they moved it around, think about how many unique different types of inputs are gonna be coming into that.

[00:00:21]
That's gonna create a lot of cache. And think about how relatively low percentage there is of reuse. Meaning, yeah, we're creating all these cache entries, but it's very unlikely that we're hitting hardly any of these cache entries. In other words, most of the inputs are unique and novel and the first time that the functions ever seen them.

[00:00:41]
So the profile that you wanna look for is a function that it's a rather small constrained set of inputs that you expect to come in, and you expect for those inputs to be repeated a lot. That's when memoization is actually a really good technique. But I often hear people say, well, if memoization is so magical and awesome, why didn't JavaScript just memoize every function by default?

[00:01:03]
And the reason why is because we don't wanna just have runaway memory and terrible performance in a different way. So in those places where it's helpful, this is a great tool to pull out of your tool belt, but be careful to analyze which types of functions you're using a technique like that on.

[00:01:23]
All right, so that is our option three solution. Now, we're going to switch gears for our fourth and final solution to the night styler. And I'm going to forewarn you that as we dive into the next several slides, it is going to be a fair bit more complicated to wrap your brains around.

[00:01:44]
So just preparing you right now, if you need to refill the coffee cup, make sure you're ready to dive into this. It is, I think, one of the most mind-bending aspects in all of DSA. If you've been able to follow along at least partially with recursion, it's gonna take that to a whole another level in a somewhat ironic sense by not doing any recursion at all.

[00:02:08]
We're gonna be able to calculate all the same things that we were just calculating, the count and all of that, but we're not gonna use any recursion at all. And it's going to run significantly faster than the memoized version of recursion. And it's not gonna use any memory.

[00:02:24]
So it's like the unicorn solution that's both less memory usage and significantly faster. And you're wondering, what is this sorcery? How are we going to do it? This technique is referred to, in the general terms, as dynamic programming. The good news is you've actually already learned one form of dynamic programming, which is top-down dynamic programming, otherwise known as memoization.

[00:02:50]
But there's another form of dynamic programming, which is what usually people mean when they use this phrase, and it's called bottom-up dynamic programming. So we're gonna go in reverse. In essence, that's the idea that you should have in your mind from now. And there's another term for that, this is referred to generally as tabulation.

[00:03:11]
Tabulation should imply to you that most of the time when you're going to employ this technique, it's when you are counting things, when you are tabulating things. So it might not be as useful of a technique, for example, to calculate the acyclic paths where we weren't counting anything, we were just enumerating all the possible different paths.

[00:03:36]
You probably wouldn't necessarily want to apply this technique in that case. Tabulation is something that should evoke that idea that I wanna count things, I wanna find out how many things are doing. Another example might be if you were trying to come up with a bottom-up tabulation. Remember one of the warm-up problems I posed to you was calculating the size of the largest island.

[00:03:58]
Well, that is counting because we're counting the units of the size. As a side note, I don't think that that problem can actually be done with tabulation because there's another characteristic here, which is that you have to be able to define an ordering for the tabulation to occur for this technique to work.

[00:04:18]
And I know that may not make much sense, but you have to be able to go in a deterministic order through your data to be able to get a tabulation solution. And with the island's size problem, if you start from the top left of your grid and you work yourself downward and rightward through your grid, that might seem like a deterministic order to go through that.

[00:04:44]
But unfortunately, you would miss parts of the island that might have curved back around and you hadn't seen yet. So you would have to go in multiple directions, and you can't really go in multiple directions at the same time, or at least I haven't been able to figure out how to do so.

[00:04:59]
So I'm not convinced that all problems that are counting can be done that way, but there are some that can, and this is one of them. So we're gonna learn this technique. So this slide I originally used as a way to help folks get some sort of mental picture of what's going on.

[00:05:20]
It's somewhat misleading, but it's metaphoric. So I want you to not try to take too much or infer too much from this. If we look at the tree and we think about a tree in a physical sense as having leaves, and if we went up to the tree, and we just shook it.

[00:05:36]
And I'm talking about like in the fall time when leaves are about to fall, and we just shook the tree, and all of the leaves on the end of the branches just started falling down. And if we had laid out ten buckets underneath this tree, conceptually or metaphorically, we can think of all of those leaves as falling into one of those buckets.

[00:05:55]
Now, here's why this is not actually an accurate way of thinking about tabulation because you don't need just one tree, you actually need all ten trees. So if all ten trees were in the exact same spot and we shook all of them at the same time, and all of their leaves fell into one of these ten buckets, we could then go through the bucket for bucket 4 and count how many leaves landed in the bucket 4.

[00:06:24]
And it turns out there would be exactly 168 leaves in that bucket, which is the number that we're looking for. Remember in our running example, the (4, 6), the answer is 168. If we took all ten trees and we shook all their leaves off, and they could fall in only one of these ten buckets, it turns out that, not accidentally quite on purpose, there would be exactly 168 leaves in the bucket number 4.

[00:06:48]
So let's set the metaphor aside cuz it's a little bit strange, a little bit hard to imagine shaking a tree like that, and let's try to think about it. Let's try to infer what we mean by this top-down versus bottom-up. Top-down, which is what we've done before, is starting from the top of the problem, that is the statement of the problem, which in this case is (4, 6).

[00:07:10]
And we are working from (4, 6) down to (3, 5) and down to (4, 4). We're working down the tree, if you will, from the top of the tree down to the leaves. So you could think about bottom-up as what if we knew where all the leaves were without having constructed the tree and worked in the opposite direction?

[00:07:32]
What if we didn't need to recurse through the tree? What if we could just infer or understand exactly where all the leaves possibly were and then just count all of them? Run through our way up and keep track of how many leaves we see as we go up, and then we would have our final answer at the end.

[00:07:50]
What's interesting about this is that that process actually is completely independent of the starting digit that we end up at. In other words, we basically do the count for all possible digits all at the same time. And then at the end, we just say, okay, the only one that I actually care about was 4.

[00:08:10]
So I'm gonna do the count for all 10 of the digits. 5, of course, is always gonna be 0, but I'm gonna do the count for all 10 of the digits. And then at the end, simply select which bucket I wanna count, which bucket I wanna look at.

[00:08:24]
So let's try to develop some intuition for that. If we started at 4 and we were doing the top-down approach, we would branch out. Remember that's how we did it, we would say, I could go from 4 to 3. That arrow is a little off, but I could go 4 to 9 and 4 to 0.

[00:08:42]
I could branch my way outward, right? Well, what if we could go in the reverse direction? What if we could ask if I wanted to determine all of the possible paths? We've been thinking about these paths as directed arrows. But if you think about this logically, it doesn't matter which direction you went in the path.

[00:09:05]
You could start at the end of any one of those paths and work your way backward and get the exact same path. So it's not actually a directed thing, it's simply an undirected traversal of a graph. And by that, what that means is that we could actually start from each of the digits and ask, not, where could I go from 4?

[00:09:26]
But get this, what if we asked where could I go to get to 4? If I got to 4, where could I have been? I could have been at 3, I could have been at 9, or I could have been at 0. So we're actually asking the reverse question, which is the best way that I can help you to understand this notion of moving from the top-down model to the bottom-up model.

[00:09:51]
We're asking the reverse question. I'm not gonna start from 4 and go 6 hops. I'm gonna say, from all of the various places that I could have been, how many paths would have ended at digit 4 after having made 6 hops? Because that number is exactly equal to the other number, which is 168.

[00:10:14]
So we're actually solving a different problem. It's kind of like when we talked about the whole bounding box thing, and we said, do my two bounding boxes overlap, has there been a collision? And it turns out that it was much easier to ask the question, do they not overlap?

[00:10:29]
This is very similar. It's much easier to calculate and to compute the other direction than it is to recurse down. It's still kinda mind-bending and difficult, even for me and I've been doing this for years. It's still difficult, and each time I come up with a new problem, it's a little bit more difficult.

[00:10:47]
It's still difficult for me to try to prove to myself that it either can or cannot be done with tabulation. This is one of those deeper areas that takes a lot of practice. So I'm not suggesting that you can just master this at the first time you try it.

[00:11:00]
But I'm gonna walk you through how to derive a solution to this problem. And hopefully, some of those principles will stick with you so that you can try it on other problems. So if we were asking what digits could I have been at when I arrived at 4?

[00:11:18]
We then could ask what digits could I have been at that I arrived at 3? And then what digits could I have arrived at 8 and so on? So we're just gonna work our way back up the tree, so this is the bottom-up tabulation.