Visualizing Dynamic Programming

[00:00:00]
>> All right, so let's visualize it this way. And these slides, these next several slides, are designed specifically to help you visually see what kind of code algorithm we're gonna write. So we've moved from the metaphorical or the theoretical into. I'm now trying to help you set up.

[00:00:17]
Okay, that sounds cool in theory, but I have no idea how to code that. And I'll show you that it's actually pretty straightforward to write code for this idea. We know that there are only 10 digits, so there are only 10 buckets. And if we could compute all of the possible six count paths for each one of those numbers, as I've done here, then it's a trivial question to say, well, what if I started from four, what would that number be?

[00:00:43]
It's 168. What if I started from two, what would that number be? It's 104. So we'd already know the answer to all ten digits up front and then it's just simply selecting that one. So how do we do that? How do we get those 10 buckets computed. What we're going to do is start out with the 10 buckets initialized to 0.

[00:01:02]
That should be pretty self explanatory. And I've notated below these ten buckets the nearby keys. Because this is key to us, this represents the going backward along the path. Where could I have been to get to zero? I could have been at four or six. Where could I have been to get to one I could have been at six or I could have been an eight, okay?

[00:01:24]
You'll notice above the set of buckets. I've got a series of ones. That's kind of like the metaphorical leaves that are falling into the bucket. But that is going to be our temporary count set and that's where our counts are going to grow, okay? So what we're going to do as we set this up is we're gonna go through all of the digits.

[00:01:42]
So we're gonna basically have a loop that goes 0 to 9, all ten digits. For each of those digits, we're going to go through their nearby keys. So on average, we're gonna go to 2.22 other places. A total of 20, if you counted out. There's a total of 20 possible places that we're going to visit.

[00:02:02]
So we've got 10, basically times the 2.22. On average, we're going to end up going to 20 other places. And we're going to ask what is your count, and add that in to our count. So we're basically saying for the zero to figure out that count, we're going to say where could I have been?

[00:02:26]
I could have been at four or six. What were the counts that four or six could have had at this moment? Well, they just start out at one. Remember, we defined the base condition as if you don't move anywhere, if your hop count is zero, you're just on the digit and that's one.

[00:02:40]
So, we're gonna grab those two ones, add them together, and that becomes two. And then we're gonna move on to the next digit. The next digit is one, and it could have been, at six, and eight. So, we'll go grab those two ones and add them together. And then we'll do the next thing for each of these.

[00:02:54]
And you'll notice that many of them end up as two. A few of a couple of them end up is three, the five one again, always going to be zero. We could skip over doing the five work, but it just, it's a nice clean, so you don't have to like remember that we're skipping it over.

[00:03:10]
So it'll just keep being a 0 the whole time. So that's our first pass when we were at hop count of six. We've done one layer of the tree, if you will. We got to go up to the next layer of the tree. So what we're going to do is take the current counts and slide those up and start again with zero in the bucket.

[00:03:29]
So it's almost like we've got another set of buckets that we keep pulling from and adding into. The metaphor starts to get really strained here, but I'm hoping that it's not too far afield for you. So we're gonna repeat the same thing again. We're going to start back over at zero.

[00:03:42]
We're on another iteration of the loop. Our hop count is down at five. We're on our second iteration, so our hop count's down at five. We're gonna start at zero and say, where could I have been? I could have been at four and six. We're gonna go grab those two counts and add them together.

[00:03:56]
So that becomes six. And then we're going to do the same thing for the rest of those digits. Go and find all of the places that they could have been and add their previous counts together. And that's how many places. So at this moment, what this tells us is that if I were to start at zero and only make two hops then I could have done six paths.

[00:04:20]
You see that? Because the six is the number of all the places that I could have been and all the places that they could have been. All the places I could have been and all the places they could have been. We've already calculated and that number is six.

[00:04:40]
And that's why that's in the 0 slot. So we're just simply inferring that how you could get to me is the same as how I could get to you. And that was the original question, we wanted to know how many places, how many ways could I get to you?

[00:04:56]
We're just asking the reverse question, how many ways could you have gotten to me? And by keeping track of all the counts as we go we always know that number to add those two or three numbers together. So we'll do it again, we added two 6's together and got 12, we added two 5's together and got 10, and so forth.

[00:05:17]
Now, we're on iteration four. Hop count is continuing to go down. We've added a 12 and I'm sorry, We added a 12 and a four and six, a 16 and a 16. Together, excuse me to get the 32. We added a 10 and a 16 together to get the 26 and so on.

[00:05:40]
So we just keep doing this running through. It's the same loop visiting, the same neighbors over and over again grabbing their previous count. Once we're done, sliding the counts up and doing it again on spurred on sliding, the counts up. And this is the final time that we went through.

[00:05:55]
We recalculated the 168. Now that our hop count goes down to 0, we don't need to do anything else, but simply select the 168 answer they're in position for. So think about the memory usage of this. We have one array of ten numbers in it. And we have a second array that's kind of our temporary count, like we're remembering it for the next iteration, and then for.

[00:06:21]
So you can basically say, we got two arrays of ten elements, right? And we have a 4 loop that goes through ten iterations to count all, to get through all the numbers. And for each one of those does an average of 2.22 other operations. So we basically have 20 operations to go through.

[00:06:43]
The reason it's 20 is because when we get to 5 there's nothing to do, right. So it's not actually 22 [COUGH]. But we do 20 total operations times the number of hops. So countPaths is an O of n that we can calculate as n times 20. And that works out to an O of n of n.

[00:07:06]
Which is referred to as linear. You might remember the big O graph that we talked about before. And there's only one other, there's only a couple of others that are lower than linear. We have logarithmic and we have constant. Linear is well within the green zone. If you can write a linear algorithm for something, it's generally quite safe to put out into production because it's very unlikely.

[00:07:34]
That it will grow in such a way that the performance fails for you. So we now have constructed a linear solution to what was previously an exponential solution. We're getting the same answer, and by the way, there's constant memory usage. It's O of 1 constant memory usage. And O of n computation time.

[00:07:56]
It's unlikely that you will run across very many algorithmic outcomes in your career. Where you end up in this unicorn scenario where you have perfect memory, usage and linear computation time. That's almost as good as it gets. It just happens to be that this problem is well set up for that.

[00:08:18]
What are some of the characteristics of this problem that do set it up for that? Well, there's a very small set of buckets. There's only ten buckets, actually nine. There's a very small set of possible buckets. If the nature of your problem is that there could be millions and millions of different buckets, it's still gonna run in linear time.

[00:08:38]
But that's gonna be a million n instead of 20 n. So there will be some performance penalty that you will pay to do a million n versus 20 of them. But it still gonna be a whole lot better than if you wrote the recursive version of it. The recursive version of it even with the memoization because yes the memoization will give you back a much faster performance.

[00:09:01]
But at the trade off of a ton of memory usage. And here we get constant memory usage. So, hopefully some of parts of that conceptual approach are not completely confusing to you. I know that it is a foreign concept. This is not how we typically solve problems. But discrete math, tells us that those, path and graph theory and a lot of math and science.

[00:09:27]
They tell us that if we solve two equivalent problems, and one is much easier to solve, then that one's the better one to take. And that's what we basically said, is I'd like to solve a different problem that gets me the same result and do a whole lot less work to do it.

[00:09:43]
And that's what we end up with here. Let's try to switch over to our code and write the dynamic programming tabulation bottom up dynamic programming version of countPaths.