Skip to main content
Loading Explore guides…
Dynamic Programming · Acedra
Home
Explore
Computer Science
Dynamic Programming
Sign in to save
Chat
If YouTube asks you to sign in, open the video on YouTube.
Watch on YouTube
Reload player
Transcript
734 segments
Copy
Hide video
0:03
Hey programmers, I'm Alvin l come to our course on dynamic programming. So dynamic programming is one of my most favorite topics to teach. But unfortunately, I feel like dynamic programming also has a reputation for being a very difficult topic. That being said, I think dynamic programming can be very intuitive. If we actually take a nice gradual progression through the material, right? A lot of students have this habit of just trying to attempt a pretty hard dynamic
0:28
programming problems, without going through the necessary steps of really understanding the material, right? It goes without saying, if you want to do well on those data structure and algorithm interviews, you definitely need to know dynamic programming. So I hope to give you all the background knowledge, you need to really crush those types of problems. Now, that being said, What problems are we going to solve throughout the course? Here
0:47
are a few examples. So one question I can ask you is to calculate the fourth number on the Fibonacci sequence seems like a very easy problem, can also ask you to count the number of different ways to move through a six by nine grid, or something different, like given a set of coins? How can we make 27 cents in the least number of coins? A final example would be given a set of substrings? What are the possible ways to construct a
1:08
string potent pot? And all of these questions really fall under the umbrella of dynamic programming. And this is really why I think the topic has such a bad reputation or being very difficult, because the problems ranged so much, right? It looks like these problems are totally different. And there may not be any underlying mechanics that we can use to tackle all of them. But the short answer is, we really can if we have the correct way of
1:32
thinking about these problems. That being said, let's go over the overall format of this course, in this course, I think our key to victory is going to be to really visualize all of these algorithms, right? So we're going to spend a lot of time drawing things on the whiteboard, as well as visualizing things with animations. To me all the heavy lifting on an algorithm interview is really done when you come up with that picture, right? When
1:54
you describe that process, and then translating it into some code is really the easy part. Right? The hard part is designing the algorithm in the first place, right? So we're going to draw out of things to make sure we understand the structure of the problem, as well as coming up with a solution. And then once we're really happy with that pen and paper process, then we'll hop into my editor, and we'll solve it in some code, we'll probably have to go
2:16
back and forth, until we end up with an algorithm that runs in an efficient amount of time, right. So it goes without saying, we're also going to analyze the time and space complexity of all of our solutions. I'll be writing my code in JavaScript, but you'll find it very easy to translate our solutions into the language of your choice. So in this course, on dynamic programming, we're going to divide the material into two main parts. Part one is going to
2:38
be about memoization. And then Part two is going to be about tabulation. And don't sweat it if you have no idea what those two terms refer to, don't worry, we'll reach all of that material step by step together, I think you're going to realize if we actually learn these things in all very logical progression, we're almost like discovering these algorithms. And I don't just have to tell us what the algorithms are. So in terms of prerequisites,
3:00
I won't assume you know anything about dynamic programming, but I will assume that you understand a little basic recursion, as well as some basics of complexity analysis, right. So you're sort of familiar with big O notation. And I'm sure that we'll be able to review some of that notation as we move along. So I think with all that out of the way, and no further ado, let's hop into the course. Alright, so where should we start? Well, I want us to
3:25
really ease into this new topic. And so what we'll do is we'll start by attacking a problem that you probably seen in the past that is I want to solve a Fibonacci problem. And so for us, we'll have a particular phrasing of the Fibonacci problem. What I want to do is write a function fib of n that takes in a number as an argument, and I need to return the nth number of the Fibonacci sequence. And just to review, how does the sequence
3:46
work? Well, the first and second number of the sequence is just one. And then at any point in time to generate the next number of the sequence, you can just sum the previous two. So for example, these are the first few numbers of the Fibonacci sequence, right starts 112358, and so on. What I'm saying is your number needs to take in like a position of the sequence. In other words, if I asked you for the seventh Fibonacci number, you need
4:07
to return the answer 13, right? Because the seventh bonacci number is 13. And how do we actually calculate that 13? Well, logically, it's just a sum of the previous two elements, that is five plus eight gives me the 13. So very, very classic function here. And to really get us going for what we do later on in the lesson, I'm going to require us to solve this one recursively, right, it's really going to be at the heart of a topic for today. Why
4:30
don't we kick things off by quickly implementing the classic recursive implementation of a Fibonacci function, probably in this function a few times in your programming career, usually one of the earliest examples of recursion that we face. So we'll just lay out the classical notation here. So I want to take in a number and and I want to return the number of the Fibonacci sequence. Like we expect, the base case is just about, you know, the first two
4:53
numbers of the sequence. In other words, if I'm given some n, that's less than or equal to two, then what I should do is just returned one. And I'm reading this because hey, the first two numbers of Fibonacci sequence are exactly one. But in the recursive case, in general, what I can do is just return the sum of the Fibonacci number right before the one I'm asking for, as well as the Fibonacci number two before the one I'm asking for,
5:16
right? Again, the kind of baked in recursive nature Fibonacci is to calculate some Fibonacci number, you can take the sum of the previous two numbers in the sequence right. Now, of course, we should test our code for some correctness, what I'll do is call a few examples of this fib function. So I'll try fib of six, seven, and eight. And I shouldn't get the answers of 813 and 21, respectively, right. So let's give this a go. I'll run this in some JavaScript.
5:44
There we have it right. 813 and 21. So this is a very, very classic implementation of Fibonacci, you've probably seen this many times before. And we did solve it recursively. And really, what I want to do is give some a larger number to this fib function. So what if I asked for, let's say, I don't know, the 15th Fibonacci numbers seems like something reasonable to ask for. So if I give this code a shot, it looks like the first three calls
6:07
of bonacci do work fine, right, I get 813 and 21. But the fourth call is actually still running, right, my program actually hasn't finished. And this is a big issue with this type of implementation with Fibonacci. So obviously, this Fibonacci function needs some work. Let's go ahead and head to the drawing board. Alright, so it's apparent that our Fibonacci function is correct. And that returns a proper result. However, if we give it a
6:30
large enough value of n, it's pretty slow. That is our function has correctness but lacks some efficiency. In the long run, we definitely want to improve this implementation of a recursive Fibonacci. But to do that, it's really important that we identify exactly where there's even room for improvement. And to do that, I think we should draw some things. This is something I think students actually need to work on. Students have this habit of trying to like
6:51
picture everything in their mind. And that works for some easier problems. However, when we want to tackle more complex problems, if we just try to capture all this information, just mentally without drawing it on, like pen and paper, or marker and whiteboard, or chalk and chalkboard, you're going to really lose track of the finer details in these structures. So I want us to be very, very methodical, and we're going to draw really how you should
7:11
visualize a problem like Fibonacci. And so over to my drawing, let's say that I wanted to trace through what happens when we call a fib with the number seven. That is I'm asking for the seventh number in the Fibonacci sequence, I know that in the long run, I should get back to 13. Right. 13 is the seventh number in the sequence. So I'll keep that goal in mind. But over to my drawing, let's say I called fib of seven, I'll denote that by really
7:34
drawing a circle with my value for n inside. So I think about this call to fib of seven, what is it going to do? Well, I know that seven is not the base case, right? Seven is not less than or equal to two. So this call is going to branch out into some more recursive calls. In particular, on its left hand side, I'm going to call n minus one, which is six. On the right hand side, I'm going to do n minus two, which is five.
7:56
And at this point, I carry over the same logic for the other nodes have the structure, right, if I look at the six node, if I'm routed right there, then that will have a left child of minus one, so five, it will also have a right child of minus two. So four, you can start to see a pattern where really this recursive structure just visualizes as a tree, which is really neat. I hop over to this five node, it will have some children, right, minus one
8:20
on slept minus two on its right. And we will actually just continue this process for most of these nodes. But let's say we pause right here. So you'll notice that these notes that have pointed to in red, they're actually the base case, right? For those nodes, I have values of two or one. And I know that those function calls will return immediately. More importantly, that means they don't branch into any further calls. So I don't want to
8:43
start flushing out the tree of those nodes. Instead, I look at things that are not the base case, right? That is these nodes in yellow. So I'll continue to flush out this tree, but not branch out further for the base cases. So at this point, I built out my entire tree, and I stopped fleshing out the tree whenever we had a base case scenario. So this is actually the full recursive tree. Remember that the numbers inside of the nodes here represent the end that we passed in. That being said,
9:12
if we have this visualization, how does this tree really calculate the Fibonacci answer? Right, so let's start to break it down over here. Let's say I looked at some note, in particular, this base case note of two, right? I know that this note is a base case, so it's going to return the value of one according to my base case, when we say return, that really just means return to your caller right return to your parent. So this note of two
9:34
is going to return one to its parent of three. In the same way, this node on the right hand side of one is also a base case, two will return one, both of those values that are returning, they go back to the parent of three, and three is actually going to add those two values up. One plus one is two. And this makes a lot of sense because we know that the third Fibonacci number is two. So we can continue this process. Okay, this node over here. This
9:59
is also a base case. So it returns one. And now the parent node of four is going to sum up both of its children values. Two plus one is three. And that makes sense in itself, because the fourth Fibonacci number is three. So you probably got the picture. Now let's speed things up. For all of these base cases, I know that they're going to return one to their parent. And for all parent nodes that have both of their children ready, that is
10:22
both of their children returned, they're just going to add up those values. And this process just continues all the way up the tree, right? Just adding our left and right children. To get the answer that we should return the very top of our tree at the root of our tree, we get the final result of 13, which makes a lot of sense, because at the start, we said that, hey, the seventh Fibonacci number is indeed 13. So now that we have a robust understanding
10:46
of how to visualize this fib function, what do we actually know about its speed? What do we know about time complexity. And so you may have heard offhand people mentioned that a classic recursive implementation of fib is going to be two to the n in time complexity. And that is the case however, you really understand the reason why. So hidden in this picture is the reason why Fibonacci for us is going to be two to the n in terms of its time complexity.
11:09
However, something that's kind of unfortunate about this drawing is it's asymmetric. And that's, I think, a big reason why students have a really hard time convincing themselves that a function like this has a two to the n power time complexity. So here's what we'll do, why don't we warm up and kind of go through some basic understanding of time complexity? And I promise we'll answer that Fibonacci question. So let's do a little warm up. Let's
11:30
say that I gave you this foo function, notice that it's different from our fib function, right? It's similar in that recursive, this function is kind of arbitrary, it actually doesn't calculate or solve any particular problem. So if I wanted to visualize how this foo function behaves, let's draw it out. Let's say I initially call it the top level foo of five. I know five is not a base case. So it's going to call upon n minus one, or it's
11:52
going to call upon for four calls three, three calls to two calls one, and then here, we've actually bottomed out at a base case. If you look at the number of calls I made, I basically made exactly five function calls. Which makes sense, because in terms of our base case, where do we stop once we hit a number less than or equal to one and every recursive step, we just subtract one from our current value of n. So overall, I have five calls here.
12:16
But if I generalize that, for any arbitrary input, I know that in the long run, I'm going to have about n different function calls recursively. And so for that reason, the time complexity of this is really just O of n time, right? I have to evaluate O of n different function calls. While we're at it, why don't we take a look at the space complexity? Well, you may have heard in past that when we analyze the space complexity of our recursive functions,
12:37
we should include any of the additional stack space that our function calls take up right, when we make a recursive call, we add that to the call stack, and those must be tracked by our computer. And so since we have about five or n different function calls added to the stack, before we hit our base case, you can see that the space complexity of this code is also O of n space, overall, we're looking at O of n time and open space for
12:59
this function. Pretty straightforward stuff, right? Let's look at another more involved function. So let's say I gave you now this bar function, it's another arbitrary function, it's very, very similar to foo, what you should notice is, the only difference is when we make a recursive call, we do an n minus two instead of an n minus one. So how does that actually change the time complexity of this function? So let's say I wanted to trace through
13:22
this and I made a top level call to bar of six, I know six is gonna call upon four four is gonna call upon to, to call zero and zero actually hits a base case. So this is very similar to our last example, except we kind of see that from one call to the next, we kind of take a bigger step in time, right. And so in a way, we can say that we're moving twice as far upon every recursive call. And this would actually half the number of recursive
13:45
calls we need overall. So I guess we might be tempted to say that the time complexity of this one is N over two time, but a keen observer would note that according to our bego, you know, understanding, we can remove any multiplicative constants when we have a time complexity, so N over two is the same as one half times n. So this simplifies nicely, it's just an O of n time complexity. Using the same exact argument, we can also say that
14:08
the space complexity from the stack is also open space. All right, so let's take a lay of the land, I showed you two functions that are very similar, they really only differ in how they made their recursive calls, right? One did minus one, the other did minus two. But in the grand scheme of things, we saw that they had an identical complexity class, right? We have O of n time and O of n space for both of these functions. So after these
14:30
two examples, you may be able to see the reason I wanted to bring them up, right, maybe you're actually ready to make the logical leap and make some conclusion about our classic Fibonacci recursive function. That being said, I don't want to skip any steps. I want to be super methodical, I think, if we pay the cost of understanding fib right now, and I mean, truly, like Absolutely. Understanding fib. It's really going to pay off later on in the lesson when
14:50
I slam me with some much harder problems. So let's be nice and methodical over here. Let's take a look at some other functions. Let's say I gave you this did function now. very particular Right, we'll pay it no mind. What do we notice about this did function? Well, it has two recursive calls now right inside of every single call. And they both do an n minus one. How should we visualize this one? Well, it's kind of similar to I
15:12
guess, our initial fib drawing and shape, where if we start with some initial call, let's say five, five is going to branch to exactly two children, right? Because five is not yet the base case. And for this did function, it does a minus one on its left, and also it's a right child, right. So the next level is just for next levels, just threes than twos, then just ones which would actually hit our base case over here. This is a really
15:33
nice, like, beautifully symmetric tree, right? Okay, so this is a visualization for our dib function. But what does it tell us about the time complexity of it? Something you'll hear me say a lot in this lesson is when we tackle a quote, unquote, new problem, or a new pattern we're really trying to do is just leverage our past experience, right? So when I look at this tree structure, I'm trying to notice anything familiar, right? Is there some strand
15:54
over here that I can grasp that to really feel comfortable and kind of extend my previous learnings, right? Where can I find our base inside of this drawing? Boop, right here. So if I look at this path, I've highlighted in yellow, it's really just the path starting at the root node going down to some base case here, I just designated the leftmost path. And what's really nice about this structure is just referring to the notes in yellow.
16:18
It's a linear structure that we saw before, right? If I start at the root, it just goes 5432. And one. And so I know that in general, based on my initial input of n, like the length of this path that has a number of nodes highlighted in yellow, there's going to be about n different nodes. If I kind of adapt that language for like the tree, I can also say that the height of this tree is n. So the height of a tree is really just the distance from the root
16:42
node all the way to the far this leaf, in this case, that just means the distance from our top level called Five, all the way down to a base case, which is going to be exactly five here. Something you may also hear in passing is we can say that the number of levels in this tree is also n, this term is pretty straightforward, right? When we say the number of levels, a level is just a collection of nodes that are the same distance away from
17:05
the root. So for example, here in yellow, I have highlighted level zero, this is level one, this is level two, this is level three, and so on. But if I rewind things a bit, I look at the very, very top level, there's one node here, on the next level, there's two nodes. On the next level, there's four nodes, then eight nodes, then 16 nodes, see the pattern? So let's try to generalize that. So I know no matter what, whenever we call some top
17:31
level argument for dib, we know that we're going to have one node at the top level. But to get the number of nodes on the next level, we'll just multiply that by two. And the level after that would also multiply by two and multiply to again further levels after that. And I do this a total of n different times, right? Because I know that the height of the tree, or the number of levels in this tree is exactly n. And so what conclusion Can we
17:54
make over here, we're basically saying that to get the total number of nodes, or the total number of calls a recursive function would make, you would just take the number two, and multiply it by itself about n times over. And that is really the definition of an exponent, right? This is the same as two to the nth power. So we can say that this tree structure, this recursive function has a two to the N, time complexity. Awesome. So we identified
18:18
this dip function is having a two to the n time complexity. But what do we know about the space complexity over here, I think a common mistake I've seen people make is kind of automatically assumed that the space complexity of a recursive function will be the same as the time complexity. And that might be a reasonable trap to fall into, because we know that in the long run, we're gonna have to evaluate two to the n function calls. And so I guess
18:39
that means you have to put two to the n function calls on the stack. But there's actually some nuance to this, the time complexity of this is not the same as space complexity. So let's jump in. Let's say that we made our top level call to dibba five, we know that that is added to the stack in the same way five calls for so it's that the stack, we add a stack frame for every call that we make down until just the base case, right. So at this point, I
19:00
reached a scenario where I have a base case, and I'd have about five stack frames on my call stack. And the important insight is when we actually hit this base case that I have highlighted the left one over here, it actually will return when something returns when a function returns, its stack frame is actually removed or popped from the stack. And at this point, only after I have returned from that left one, what I actually add the right one
19:22
to the stack to be explored. And this process continues. Notice that any point in time the most number of stack frames that we use up, it's exactly five, right, it's not as if we throw all of these function calls on the stack at once. And because we have such a nice tree visual, we know that the number of stack frames that we're ever going to use is really just the height of the tree, right, so the height of the tree is n like we said before, that
19:45
means our maximum stack depth is also n. So we have in space complexity coming from the call stack. So overall, for a dip function, we're looking at two to the n time complexity, but only and space complexity. Alright, so let's look at one more function. See, I gave you this very similar lib function. Notice that in its recursive calls, it does an n minus two. So by now you should be able to visualize what structure like this would look
20:09
like, say we initially called lib with a value of eight, what would the full tree look like? Well, it would just look like this. Notice that it's still a tree, right where every node branches to two children. But this time, we go by twos, right, so if I look for some familiar ground here, I've noticed that from one node to the next, I do one minus two. And this occurs all the way down to a base case. So we already know that, hey, we can
20:31
identify this tree as having a height of about N over two. So I guess that means that the time complexity is going to be two to the N over two power, right, because from one level of the tree to the next, we double the number of nodes. So that's that two times two times two repeating pattern for the number of levels and our number of levels is N over two, right? However, we can actually simplify this time complexity, you can take that n
20:54
over to in the exponent and simplify that to just an N. So overall, we're looking at a two to the n time complexity. And using our same arguments from last time, we know that the space complexity for this from the stack is also going to be N over two, which simplifies nicely to N space complexity. So we see that overall for our loop function, we're looking at a two to the n time, but no space complexity. Alright, so now it's time to look at the big picture, we looked at two toy functions of
21:18
dibben lib. And we saw that the only difference in how they made the recursive calls, right did did a minus one and lived in a minus two. And we saw that despite their differences, both functions had an exponential two to the n time complexity, and a linear and space complexity. That being said, Where does our original Fibonacci function fit in this picture? Well, you can imagine that kind of falls right in between, we know that for our fib function,
21:43
it has two recursive calls for the first recursive call, it makes it does n minus one like did did. But its second recursive call this n minus two like lib. So in a sense, it's kind of like smack in the middle, right? If you let me abuse the notation a little bit, and just talking about the time complexity, we can kind of say that the complexity of fib is somewhere between dibben lib, but we've already plugged in some values, right? You
22:04
know, that, hey, the lower bound that as Deb has to to the end, and the upper bound, that is lib has to at the end as well. So that means that our fib function must have exactly two to the n time complexity as well, right? All three of these functions have an exponential time complexity. Awesome. So that was a really complete analysis of why we have this fib function, it's evident that it has a two to the n time complexity and an N space complexity.
22:28
Right now, the bottleneck that we're experiencing is, of course, the time complexity, right two to the n overall, is not undesirable complexity. But do we really have a nice feel for what this really implies? So let's take a look at this to to the end. So what's the implication of this? Well, you could kind of imagine that, hey, if I asked for the 50th Fibonacci number, that would take you know, roughly two to the fifth power number of steps. And so if you
22:52
punch this exponent into a calculator, you're gonna end up with a result like this, this is roughly a 16 digit number. So you should have a vi for you know, this being a very, very, very large quantity. But I think that, you know, to really understand the gravity of what we're really saying here, if we expand this number, that quantity is exactly this. That's over one quadrillion 125 trillion, which is really, really interesting, right?
23:18
Because we just asked our Fibonacci function for just you know, something relatively modest, right, the 50th Fibonacci number, and it's gonna take quite literally a quadrillion steps to do that. And of course, we can probably do better. So let's work on making this faster. So if I recognize that the bottleneck for this fib function is the time complexity, I know that that comes from the number of recursive calls that I make. So what I want
23:39
to do is look for any patterns that I see in the recursive nature of this problem, let's see a quick snapshot of what the recursion for fib of seven would look like, we know that it looks like this tree just like we saw before. So take a moment, look at this tree, do you notice any interesting patterns within it? Well, one thing that I noticed is I can see this subtree rooted at three, there, I have two on the left and one on the right. And if I look at that subtree, I can actually
24:04
see it in many different places in this tree, right? This subtree rooted at three appears in a bunch of different places, it's very duplicate. In a similar way, I can look at other sub trees, let's say I root myself at four, and see that duplicate four sub tree all over the place. And it's even carries over for larger values of n like fib of five. So I see that this tree has a lot of duplicate sub trees, right? And I want to now draw a
24:28
connection between this diagram and what happens in my code. I know that if I route myself in any of these sub trees of five, I know that each sub tree is trying to answer the question. Hey, what's the fifth Fibonacci number? I know that the Fibonacci number never changes, right? If I calculate it once on the left hand side, then the answer I should get back on the right hand side shouldn't differ at all. And so what I want to do is
24:49
possibly reuse these calculations right? If I calculate the Fibonacci number over here, then I should just store that because later on it might be useful when need to recalculate it over here. I would basically get rid of a lot of the tree, I wouldn't have to travel down this entire recursive tree rooted at five. This pattern of overlapping subproblems is known as dynamic programming. And so for us dynamic program is going to be any instance
25:14
where we have some larger problem, in this case, Fibonacci. And we can decompose it into smaller instances of the same problem, we also have an overlapping structure. So for us, right, now, I see that I have to calculate now let's say fib of five, twice over to calculate the larger a fib of seven a solution. And something we're going to be doing a lot in this lesson is really trying to visualize problems in terms of like their recursive
25:36
nature. So we're going to be drawing a lot of trees. And what I'm always going to do is try to really recognize, hey, what pattern in this tree is duplicate, right? If I do some duplicate work, if I do some duplicate drawing that I know I can optimize that out later on. But that being said, let's go ahead and get to the punch line on this fib function and work on optimizing this solution. Alright, now let me discuss the plan, I think we're
25:59
ready to actually implement some code that will actually carry that plan out. Here I have our classic bonacci implementation, this was the one that we ran earlier. And it's definitely too slow, right has an exponential time complexity. So I know that overall, when I want to do is kind of capture a duplicate subproblems, I want to store any results that I get that way, if I have to recalculate those subproblems. Later on, I can just use my stored
26:20
data. And so the trick here, it's a very common programming pattern, we're going to implement some memorization. memorization is actually one of the overarching strategies we can use to solve any dynamic programming problems. And so just look at the name like why is it called memoization? Well, this refers to like, memo, right? So if I have like a memo, and let's say, like real life, it's really just like a reminder for myself. So using memoization,
26:42
I'm looking to do is store some duplicate subproblems. That way, I can just get those results later on. I think a really neat way to implement memorization in JavaScript, as well as many languages is to use some sort of a fast access data structure usually be like your hash map equivalent in the programming language of your choice. For us, that'll be a JavaScript object. And so our plan is to use some JavaScript object. And so what do
27:06
I want the keys to be, so the keys in the object are going to be the argument to our function, right. And then the value will be the return value, that we have a nice napping for a argument to the function that is a function call, as well as its return value, right. And so what I can do for my existing function is, I kind of just bake in some optional arguments. So my favorite strategy is to do this, and assign a memo to be an empty object. So if
27:36
you're unfamiliar with this syntax, in JavaScript, it's pretty useful. What I'm saying is, if I were to call our fib function, and not pass in a second argument, by default, it will create this memo, as containing a new JavaScript object that is empty, of course, right? So it's gonna be useful that way, whoever is actually testing, my code doesn't have to deal with setting up any memo object. So well, I prefer this strategy over here. And what
28:00
I want to do is treat it as if that, hey, this memo is going to store n as the key and values are going to be just the return values for this function. So what we're going to see us doing a lot in this lesson is at the start, we're going to first check for existence inside of our memo. So let's say that we're somewhere in the middle of recursion, the first thing I should do is kind of add an additional base case and say, Hey, is my current
28:24
argument n inside of the memo, and if it is, then I can just get the stored value from that memo. And I'm done. So I'm going to do an early return here, I'm going to return the value that corresponds to that memos key, right, I'm just using the original argument and as a key in my memo, and this condition is really just some classic JavaScript syntax, I'm just checking if some key is inside of a JavaScript object. So
28:48
really quick, maybe just to warm us up, if you haven't seen that syntax before. So let's say I had some object and had some properties inside and we had a name of Alvin, that's me, then it had a favorite color of like gray. And what I can do is check for an existence of a key in that object. So JavaScript keys are mostly strings, right? So I can check Hey, his name in the object. That's true, is the fav color in the object, make sure
29:18
I spell it right. That is also true, I can check for a key that's not there, like I don't know, his location and the object that is false. And so here, I'm just using that same pattern, but for and right, which is going to be a number, technically, it'd be converted into a string key, which would still totally work here. Awesome. So I have my memo fetching logic, right? I check, Hey, is this argument in the memo, but if it's not, I'm gonna have
29:42
to actually manually do the calculation, which is okay, because I know I need to do a subtree at least once. So what I'll do is I'm going to take the exact return value, right, so this is my return value in the original brute force. What I want to do is actually store that entire result inside of my memo and the key is course and write, the key you use to access is always just what your argument is. And I want to complete the original return.
30:06
So I can just go ahead and return what I just put in that memo. So I'm not really changing any return values, or I'm returning exactly the expression that I returned before. But now I'm actually also saving that value inside of the memo object. What I want to do is make sure that all of these recursive function calls are accessing the same memo. So what I'll do is I'll pass in that object to both of these calls are really important pattern
30:33
here is, I know that I only receive a new top level metal object, whenever I make a top level call, that's a fit, right, because I'm not passing in a second argument over here. However, if I look at my recursive calls, I do pass in explicit second arguments. And so they're actually going to receive the same memo object, and it would be like passed by reference, right, because when you pass a JavaScript object to a function, you actually
30:56
receive kind of that exact object, right, you don't receive a copy of it, which is really neat. So basically, I'm giving my function calls a way to sort of communicate to each other, they all have some sort of global information to reference across all the recursive trees. So this is looking good. Again, I just want to emphasize I only added a new argument over here, I added a new base case on line five, then I added my memo storing logic on line
31:21
seven, but I didn't change any of the functional logic here. Let's go ahead and run these test cases. And we'll see how our code is doing now. So moment of truth, I'm going to run this file. And notice how blazing fast our program was, I still get the results of 813 and 21. And the 50th Fibonacci number is indeed have this very large number. And it basically executed almost instantly. So let's go ahead and head back to the drawing board. And really understand
31:49
you know, what happens when we execute this sort of code. Alright, so it looks like we implemented the improved version of Fibonacci by memorizing it. And it's clear by running the program that we definitely had an impact on the time complexity. However, I really don't want us to understand you know how the structure of the recursion tree changes, once we implemented this memoized version of the code. So let's say I want to step through
32:10
an example of Fibonacci. And let's say I pass in a number six. So really, what I'm looking for here is to get back eight, because the six number of the bonacci sequence is indeed eight. So we know that we're going to have a tree that looks like this, right? This is a tree that would really be the full recursive nature. So this is how the tree would look like if I did not optimize it. And what impact do we have by actually adding this memo object?
32:32
Alright, so let's start tracing through this, I know that when I call fib of six at the top level, an important thing to know is I'm not going to pass in some memo object. So by default, my code says it will initialize it to an empty object. And the really important aspect of this is I'm going to create a new object just for the top level call. But then that same object is going to be passed down to my recursive calls, right noticing line
32:54
five. And so I'm going to travel down my left hand path, right, six calls five, five calls for four calls three, and three calls to, and right now I've hit a base case. So I know that this note of two is going to return one. So that's kind of business as usual, right? In the same way, now I need to evaluate this other note of one, which is also base case, it also returns one. And at this point, my parent of three is actually ready to compute
33:17
the sum of its children, right. So one plus one just gives me two. So I just add up those values. And now three is returning two. However, looking at line five of my code, not only is this node going to return to to its parent, it's also going to store it in the memo object, right? So the key insight is, at this point, I would add a key to my memo of three, whose value is to basically in my memo, I kind of read as if I'm saying, hey, the third Fibonacci
33:46
number is two, right? That in itself is logical. So I can just continue this pattern right? Now I start to evaluate what happens when I'm at this note of t, which is also a base case, it returns one. Now my call to four is ready to compute, right? It's going to take the sum of its both children. So it's going to do two plus one gives me three. But of course, it's also going to store that inside of the memo, right? It's going to cash that
34:08
result out to be used later on. So that means I make the N my key and I make the return value, the value, right, so I'm going to have four points to three inside of my mental object. And now here's the beauty of this memoized solution. At this point, I need to compute what happens for fib of three. However, this is actually going to hit one of the new base cases I added, right? I know that three is in the memo object looking at line two of
34:35
my code, right? It's in the memo object. And so I just immediately return the stored value. And so this call to fib of three is just going to return the stored value of two. And if I do that, I won't have to travel down the full, you know, recursive subtree rooted at three, right? I don't need to travel to these nodes at all. So I already used some stored value in my memo. At this point five is ready to return right five will take The summer
35:00
both with children, three plus two is five. And it's going to store that in the memo, right? The fifth Fibonacci number happens to be five. And now the same thing happens for six is right child. So I have to evaluate this node now. So what is the fourth of bonacci number up, that's actually stored directly inside of my memo. So this actually early returns the stored value of three, right. And again, the key insight is, it will return
35:24
that stored memo value without having to travel through that full subtree. And at this point, I can return for fib of six, so I do five plus three, that gives me eight, this would actually technically be stored in my memo as well. So I have the six of bonacci number as eight and very happy, right? The answer is eight. So it's evident that by memorizing our Fibonacci function, we definitely cut down on the number
35:47
of recursive calls, we want to visualize that we ended up with this kind of structure. Here in light blue, I have a circle the nodes that we technically didn't need to do the full recursion at, right? So these nodes of two, three and four, for this small example of my initial fib of six, I was able to kind of fetch a value from my memo and kind of forego traveling down the recursive subtree. So what do we actually know about the time
36:12
complexity of this function now? Well, I think it's really important that we always try to generalize things. So we just stepped through a relatively small example of fib of six. But how does this sort of scale? So this is the same tree? Let's see, I kind of tidy it up a little bit. So I know that in general, fib of six kind of has this structure. So I want you to take a moment, look at this. And in your brain picture, what fib of seven
36:35
would look like if I memorize with with seven, what would its sub trees look like? Well, it really just looked like this. Notice if I route myself at the seven node, its left child is still six, right minus one. Its right, Charles, still five minus two. So this still obeys the laws of Fibonacci. If I asked for fib of eight memoized, the structure would be like this. And nine would look like this. See the pattern looks like at this point,
37:00
we're just growing this like memoized chain in a linear kind of way. If you're not convinced by you know, that just like structural argument, let's say we were a little more methodical, we know that in this drawing, there is some common ground, right? Again, like I always say, when you tackle these new problems, or new patterns, try to find some familiar territory, right? Where can I recognize stuff I've seen previously. So I look at this chain, I go
37:23
98765432, right. So this goes all the way down in a very, very, very linear fashion, right, just counting down. So I know that if I just look at this highlighted chain in yellow, that's definitely just an notes, right, where n is my initial top level call. So I know that what I have highlighted in yellow is just a linear chain right there exactly n nodes. But I haven't accounted for everything in this picture, right, some of the nodes
37:48
are still in white, meaning I need to kind of work them into my description of what the shape of this tree is, well, I know that each of those white nodes is actually connected to some of the nodes, I've colored in yellow, they're kind of paired off in a way, right? For every node in my ello chain, it has exactly kind of one partner node one right hand node on its right hand edge. And overall, if I have n pairs, that means I have to end things
38:11
overall, right? There are two things in a pair. So overall, the number of nodes is roughly two n. And I know that that can actually be simplified, right? The time complexity here would be two n, which just simplifies to n time complexity. And using the same arguments we did for our space complexity, we know that the space is going to be n as well. And this is pretty powerful stuff. by memorizing our fib function, we brought it down from an exponential
38:33
time complexity to just a linear time complexity. Pretty cool stuff, right? All right, I think we're ready to graduate from Fibonacci. And what we'll do is work on a more involved problem, this one has more of a narrative to it. So say that you're a traveler on a two dimensional grid, you begin in the top left corner, and your goal is to travel to the bottom right corner of that grid. And the rule is you can only move down or to the right, that means
38:55
you can't move up or to the left, and you definitely can't move to AGL. That being said, In how many ways can you travel to the goal? That is how many ways can you travel to the bottom rate if you had a grid of dimensions, m by n. So the first thing I recognize here is looks like the grid, maybe a rectangle, not necessarily a square, right. And overall, what we want to do is implement a function that calculates this that is our function
39:17
is to take the dimensions of the grid. And so before we hop into sketching the strategy for this one, I think it's really important that we make sure that we actually understand what this question is asking. So let's say they asked us to calculate grid traveller of two comma three, that means they're asking us in how many ways can you travel from the top left to the bottom right, of a two by three grid? I will tell you right now that
39:38
the answer here should be three. Right? So there are three ways to do that. And in particular, you can imagine that we had, you know, a two by three grid, so that means two rows, as well as three columns. And we start in the top left, and our end goal is in the bottom right. And so why do we say that there are three ways to get from the top left to the bottom right? Well, they told us in the problem that we can only either take a right move
39:59
or a down To move, so one of the ways would be going right right down, right, that would bring us from the start to the end. And it would kind of look like this. In a similar way, another path we can take is doing a write down, right? It would kind of look like this. And the only other way would be going down, right, right, which would look like this path. And that's why we say there are only three unique ways to travel not through a two by three grid.
40:22
All right, so that's just one example of how we might call a grid traveler, I think what's really important to notice is try to also frame the problem as if you were given some relatively small inputs, but I think they're really important case to think about is, what happens if they give us like, basically, the smallest valid grid we can have that is a one by one grid. This one is kind of trivially simple, right? A one by one grid only has
40:45
one unique way to travel from the start to the end. And it's kind of concise in that if you had a one by one grid, there's really only one position, right? So that means that the start is really the same as the end, and kind of you already have the problem solved out the gate, because to travel from the start to the end, you kind of just do nothing, right? So the logic here is in a one by one grid, there's only one way to travel from the start
41:09
to the end, you're kind of already there. So you don't need to take any moves. Something else we might think about is what happens when one of our dimensions is zero. So let's say someone asked us to calculate grid traveller of zero comma one, this is a kind of strange question to ask because for one, if there are zero rows and one column, that kind of means that the grid is empty. So I would consider that as there being zero waste to travel through
41:32
that grid because the grid is sort of invalid in a way. In a similar way, if I asked you for traveling through a one by zero grid, there's still no grid to be found here. Right? So it should also return zero. And likewise, when either of the dimensions is zero, the answer should just be zero, right? If one of your dimensions is empty, then there really is no grid. So maybe you're catching on into why I brought up those trivially small grid examples, right?
41:58
Those kind of sound like base cases, which we can use to reconstruct a larger answer. But let's stay grounded and look at another grid. So let's say I asked you to calculate grid traveler of three comma three, right? So I want the answer for a three by three grid. Well, how can we reason that one out? At this point, what I'm looking to do is sort of frame the problem in a way where I can decrease the problem size, usually by mutating
42:21
the arguments to my function call. So let's imagine this three by three grid, as always, I want to move from the top left to the bottom, right. So I begin at this position, let's say, and so I know that overall, I have this top level problem of saying, how many ways can I travel through this entire three by three grid, let's say I took one of the moves, right, I can move either right or downward. Let's say I made the decision to move downward.
42:44
Well, if I move downward, then I would appear here now, I know in the future, I can only move to the right or downward. So now it's as if my playable area has been reduced to just this shaded region. And if I look at what I've actually done to this problem, I'm still sort of in the top left corner of some grid, where now I'm really trying to answer the question, hey, and how many ways can I travel through this two by three grid. And
43:10
this is a really important way that we're shrinking the problem size, right, I had a three by three grid initially. Now I have a two by three grid. And this is really like the relative grid from my current position, we'll say, spanning all the way to the end position. So if you look at this coordinate of like two comma three, technically, that is like not the coordinate of the person within the larger grid. This is really the size of
43:33
the rectangle that the person is trying to cover now. Right. So in a similar way, let's say that, hey, I want it to move to the right now. Well, that would also shrink the grid along a different dimension. So I'd appear over here. And now I have a two by two grid that I'm trying to solve. And if I keep following this pattern, we're gonna keep shrinking on the problem size over here. Now, I'm asking for a grid traveller of one by two. And finally,
43:56
if I take a right move over here, I'm asking for grid traveller of one by one, which I know is one of those sort of base case scenarios that I had previously. So that's going to be really useful when we actually implement this in some code. And so the key insight here is when we make a move through the grid, that is when we go right or downward, are basically shrinking the effective size of the playable area, right, our grid gets smaller
44:17
along one of its dimensions. Awesome. So I think now we're able to see that, hey, this grid traveler problem definitely has some overlapping subproblems. Right. Let's say I tried to take more of like a programmatic approach, something that we'll be doing a ton, like, basically, for every problem in this lesson is whenever we have a problem that we kind of know is going to be recursive. The move is to really structure it like a
44:40
tree, right? I want to really visualize this because I know that if I had a tree structure on pen and paper, I can implement that with just some recursive code using some JavaScript, right. So let's say that I wanted to take more of a tree based visual understanding now a grid traveller of two comma three. So I know that usually the way we do this is we encode nodes of the tree Using the arguments to this function right? Now I have two arguments
45:03
where I have the number of rows and number of columns. Whereas before for something simple like Fibonacci, I only had a single argument. So in the long run, I know that the answer I should get back is three. So just keep that goal in mind. Let's start to flesh out this diagram. So I'm going to start with that top level, column two comma three. And now I think about how this node can transition to other nodes, right? How does the State of my game
45:24
actually change? Well, I know there are really two options I can take right? You can either have one child going downward, or another child going the right word, right? Those are the two options based on the gameplay here. And so if I go down, how does that change of the number I put in the node? That is, how does it change the dimensions of the playable grid area? Well, if I go downward, then I'm reducing the number of rows by one. So that
45:49
means my left child is just one comma three. Now, if I had moved to the right, that would mean I'm reducing the number of columns by one. So my right child is just two comma two. Notice that from parent to child, all I'm doing is reducing a one of the dimensions by one, right, that means you're either going downward or going to the right, and I can just carry over this pattern recursively, right. So let's say I'm fleshing out this
46:11
node now, five, mat one comma three, then its children would be just 03. And one, two. And a similar way. If I wrote myself at two, two, then I have children of one, two, and two, one. But now let's notice something important. Here. I've kind of spotted a node where I have zero comma three, remember what we trace through in terms of the visual drawing? What is this? No trying to answer? Well, let's notice saying in how many ways can you travel
46:37
through a zero by three grid, but if you have zero rows, and there's really no grid to be dealt with. And so I think for this note of zero comma three, or really any node that contains zero, we don't need to actually flesh out its children. So instead, I'll work on recursively, drawing out these other nodes. So we'll carry over this pattern. At this point, we've actually hit I think all of our base scenarios, right. So if I look at these
47:02
notes, that have one comma one that was exactly like the affirmative base case, meaning that I know, trivially I can solve the one by one grid. In other words, these function calls are going to return one, right, in a one by one grid, there's exactly one way to travel from start to end, right, you kind of just do nothing. And on the flip side of that, for all those notes that contain a zero, they're also a base case. But they're kind of like
47:27
the negative base case, meaning that there is no way to actually travel from start to end. So for all of these notes containing zero, they should return zero to their parent, right? There are zero ways to travel through that grid. At this point, I just sum up these values at the parent node, right? So I just left these and then I add them together. And I forget what these things are saying, right? If I look at like the node one comma two,
47:49
above, it is one meaning there is one way to travel through a one by two grid, right? You kind of just move rightward. And so I carry this pattern over, I keep adding the children nodes at their parents. And this carries up all the way to the root node. And what do I know, there are three ways to travel through a two by three grid. So although there's like a narrative, and there's some, you know, cute story behind this problem, it's really
48:13
just a spin off of Fibonacci. And that's going to be the case with many of these dynamic programming problems. So we've confirmed that there are three ways to travel through a two by three grid. And there's also some other information encoded in this tree. I know that whenever I took like a left hand edge in this tree that I presented the choice of going downward. And whenever I took a right hand edge in this tree, that represented the decision
48:36
of moving rightward. And so if I have that pattern in mind, that not only have I been able to count the number of ways that I can win the game, but I also know exactly which combination of moves lead to a solution. One of the ways to win this game is to go down, right, right. Another way is to go right down, right, and the final ways to go right right down. So we can glean a lot of information just from the same tree structure. Cool. So
49:03
I think that's enough drawing for now let's go ahead and implement this in some code. Alright, programmers, here we are back in my text editor. Let's go ahead and implement this grid traveler function. So you want to go with that recursive strategy. So I'll start by just laying down my base cases, I already refer to the fact that hey, one of our base cases is we have a one by one grid, just go ahead and return to zero, right? So that's
49:24
really easy to do. So I'll check Hey, if m is one, and n is one, then the answer is just trivially one. Right? Then along with that, I also have the base case when I had like an invalid grid. That means if either of my dimensions is zero, so I'm using an order here, right? If either dimension is zero, then your grid is empty, which means there's definitely no way to travel from top left to bottom right of that grid. Cool. Then my
49:51
recursive scenario is very straightforward. All I need to do is get the sum between me going downward and me going rightward, right. So if I go Down number n is the number of rows, if I go down that I'm decreasing the number of rows affected rows, that is by one, but I keep the same number of columns. And then in a very symmetric way, if I move to the right, that means I still have the same number of rows. So I keep him, but I decrease
50:16
n, right, I have one less column. So this code is looking pretty sharp, really just some reminiscent Fibonacci style code. Let's go ahead and give this a run. So I'm running a few examples over here. And these are the expected results. In some comments, we'll go ahead and bang this one out, grid traveller. Cool. So I get the first four results. 1336 looks like it's working just like a charm. However, for this last example of an 18 by
50:42
18 grid, looks like my programs hang right now, it's actually a little too slow to calculate an 18 by 18 grid, so you probably see where this one's heading. Let's go ahead back to the drawing board and really understand a why this code is fairly slow. Alright, so here we are back in the drawing board, because it looks like we hit a wall when it came to our recursive implementation of grid traveller. That being said, I think implementing the
51:06
brute force solution here is actually a really logical first step. And now we can just focus in on where there is room for improvement. So our first question is, you know, what is the actual time complexity of this implementation? Well, I know when I call a grid traveller of two, three, the full tree would explore is this right. And like we said, in our Fibonacci, to understand the time complexity here, it's really about to understand the number of function
51:30
calls we make, which is really the number of nodes in this tree. And of course, I want to generalize my understanding for any large inputs. So I know that this tree sort of looks, you know binary in a way, meaning that a node can branch to up to two children, which makes sense, because from one position of the grid, I have two choices to make, right, I either go down or I go to the right. But that being said, I need to realize what the height of
51:52
this tree is. And this one's pretty interesting, because out the gate, we actually have two input arguments to our function, I'm given two numbers, m and n. And since this function contains two inputs, it shouldn't be the case that our final complexity analysis actually describes it in terms of those two number inputs. So what I'll do is try to recognize the height of this tree. And so I'll just choose some path from the root to the leaf.
52:16
And kind of in the recursive sense, that means I take some path from my top level call all the way down to the base case, and preferably the far this base case. So I know my base cases are either when one of my arguments turns to zero, or when both of my arguments turn to one. And I think in general, the farther base case would be a scenario where both of my arguments are one. So here I have a path highlighted that ends in a one one. And in
52:41
general, I know from one node to the next, what I do is either decrease the M by one, or I decrease the n by one, it's never the case that I can decrease both of the numbers by one, because that would kind of entail that you're moving diagonally across the grid, which is not allowed in the gameplay. So if I can either subtract one from em, or subtract one from n, and overall a path from my initial input down to a space, like one one is going
53:07
to have a distance of n plus m, we basically had to subtract, you know, n and m from your initial node to reach that bottom level of one comma one, that kind of tells me the number of levels in this tree, right using the same arguments as before, it's still the case that most of this tree is going to be binary, meaning that a node branches to two children. And so I have that two times two times two pattern for the number of levels in this tree are
53:32
saying that they're n plus m levels. So really, the time complexity is two to the n plus m power, right. So still some sort of exponential, that was just sort of the multi variable exponential, because I have two variables of m and n. And likewise, for the space complexity, you know, the space complexity, in general for recursive code is just going to be the height of the tree, the height of the tree gives us the maximum stack depth of the recursion. In this case, it'll just be the number of
53:58
levels still, which is n plus m. Cool. So obviously, the limiting factor here seems to be that time complexity of two to the n plus m time. Alright, so you probably anticipated the time complexity of this one being exponential. That being said, I think it's really important to still have a nice argument to you know, say what the time complexity is. That way, you can get a massive buy in from your interviewer right. So don't skip the steps of trying to
54:21
draw it out and actually defend your reason for why the time complexity is exponential. But let's try to improve this now. Is there any room to actually improve the runtime of this function? Well, here's that same drawing, right? Just sort of cleaned up. So I have grid traveller of two comma three, and this would be the full tree. We sort of already know now that I have this recursive tree structure. What I could possibly do is notice any duplicate
54:44
work, right? Is there some work I can prevent myself from doing here. So take a moment and really remind yourself of the actions we took in the Fibonacci problem. And see if there's any patterns in this tree, probably from the gate, you notice that? Oh, I have some duplicate sub trees right? Have one comma two. So in these the two highlighted sub trees in blue, that's sort of asking the question, hey, what is the total number of ways I can travel through
55:09
a one by two grid? That being said, I think there's even more sub trees that correspond to that particular problem. What if you look at this far right subtree of two comma one, if you really, really think about it, asking the number of ways to travel through a one by two grid is the same as the number of ways to travel through a two by one grid, you're just flipping the rows and the columns, but the total number of ways should be exactly
55:33
the same. So that's actually a pretty interesting way you can optimize this solution. So I can still memorize it. That is I have these duplicate sub problems. But possibly a really cool insight we can make in this problem is, you can also sort of flip of the arguments. In other words, if someone asked you, for grid traveler have a comma b, then that would be the same answer for a grid traveler of B, comma a, write the order of the arguments technically doesn't
55:58
matter here, until we can totally encode that in our memo object. That being said, punchline here is, we better memorize this one. So I think let's hop to it. All right, here we are back in my text editor. And hopefully, that diagram of how we can improve the time complexity for this one, make some sense, let me go ahead and kill this program still running. And my computer's fan is actually going crazy. Now it's running the entire time.
56:22
Let's go ahead and memorize this one to the beauty of you know, solving these dynamic programming like problems is if we have the initial strategy of implementing, like the brute force recursion, and we wrote like a very well formed recursion, meaning that I actually use return values, and I reconstruct the sub solutions all the way up to the tippy top. Because I have a really nice recursion here. memoization is a very like formulaic
56:46
pattern. So it's going to be almost the same strategy, we did have Fibonacci, even other problems that we do in this lesson. So we're going to bake in my default mental as an empty object. And then along with that, I'm going to add my memo checking logic. So I know we're here in general, and to check, hey, are the arguments in the memo, right, I need to key into my memory object using all of the arguments. Now I have two arguments. And since both of
57:12
the arguments combined, sort of dictate the output, I need a key that sort of contains both of those in JavaScript keys are either strings or symbols. So for us right now, really, strings is the most relevant one. So what I'll do is I'll concatenate both of these integers together. That way, I have a string which I can key into the object with. And we'll all definitely want to do is also maybe separate them with a comma, let's say, so
57:36
I'll say like key equals m plus a comma, plus, and, and the reason that you probably want like some sort of separator between these two arguments in your key is to make sure the numbers don't get misinterpreted. So I've actually ran into this issue in the past, can you imagine like, if I had a scenario where, let's say m, was 42. And then we'll say n was a number three. So what I don't want to do is just make my key, something like four to three, because this isn't going to uniquely identify
58:15
the exact input argument, right? Because if this was just my key, then I guess I have the same key for a totally separate set of arguments. If I gave you four and 23, right, both of these combinations of very different arguments would lead to the same key, they would collide at the same key. So instead, I'll prefer to put a comma between them right now I know without a doubt that this key corresponds to four comma 23. Right. So that's why I put
58:43
a separator between them. And depending on the language that you know, you're choosing for interviews, you can find a very similar construct. Cool. So now I'll go ahead and check, hey, if my key is in demo, then I have the Result Cache already. So I could just return net cash value. So return memo at key. And then what I want to do is look for my old return value, right? So here's where I actually do the manual recursive calculation.
59:09
Before I return that I want to store it in my memo, using the same key and then return that thing, I just put in the memo just completing the old return logic. Cool. So you've seen this pattern before, I just want to emphasize a few things. Now it's the second time we're seeing it. memoization, for me, at least, is a very, very formulaic thing, right? So I always take the exact expression that I returned previously, and I put that entire
59:34
thing in the memo object, right? Notice that my key encodes the arguments for this function, right? Mnn. Something that I've seen students do in the past is do like very heavy handed logic, where they try to, you know, check if the child call is in the memo. In other words, don't write any pre emptive logic where you check Hey, if you know m minus one And so if you like concatenate those two things together, don't check if like your child's
1:00:05
key is in the memo, right? So imagine like, this was my key right now. Right? don't check if that is in a memo. When you write logic like that, it ends up being very, very duplicate and a little harder to debug, right? Instead of writing your function as if it's, you know, reasoning for its children calls, you know that once you actually evaluate those child calls, they're going to cache themselves, right, they're eventually going to check this
1:00:31
if statement anyway, alright, so don't do any like the look before you leap logic, just make the recursive call. That way, every recursive call doesn't like self service, right? So I prefer this way implemented. And with that, let's go ahead and run this code. So I'll give this a shot grid tremor, I still have that 18 by 18 grid, which took quite long last time didn't actually finish while I was waiting. Looks like I'm still hanging here,
1:00:56
because I'm actually missing a little bit in my code. So take a moment, see if you can spot it, I forgot one really important thing. So I have the logic of checking if my key exists in the memo. And I also have a logic of storing something in my memo if the key doesn't exist, but what I failed to do was actually passed down the memo object to all of the recursive calls, I want to pass it down over here. Remember, the trick is only
1:01:18
top level when someone calls like two comma three for grid traveller, then we're going to initialize a brand new empty object, which will be shared for the rest of the recursion, because it's passed down by reference at this point. So that's a common mistake. Let's go ahead and run this now. Nice. And there we have it. Look how quick our last execution was over here now is the expected answer for an 18 by 18. grid. Cool. So here's
1:01:42
what we'll do, it's evident that we definitely set up the execution of this one, let's head back to the drawing board to wrap up this problem and really see how we cut down the complexity here. All right, so it looks like we definitely improved the runtime of our function. But I want to really understand you know, what the big O complexity of our improved function is now. So sort of a way we constructively argue for what the new time
1:02:05
complexity is, is to think about where the values of the nodes that will actually have to travel through. So let's say I looked at this example, I wanted to find the number of voice a traveled through a four by three grid, I know in general, there would be a top level node, of course, four comma three. But in general, that refers to m n, right? So I'm trying to think in a very general way right now. And so I know when it comes to
1:02:28
the other nodes of this tree, they're all going to sort of at most be four comma three, but then probably be less than that, right? They have like a range of values for the nodes. It's not as if to solve grid traveler, four, three, I would have to solve 530, right, that would be a larger grid. That doesn't make sense here, right? I'm shrinking the subproblems, only in this rendition of grid traveler. And so if I think about some possible values here,
1:02:54
I know that if M is for top level, then all of the values for m in the rest of the tree would be from zero all the way up to and including four, right, it's never going to be bigger than four. In a similar way, since n is three here, the only possible values for n in the rest of my tree are zero through three. Right? So roughly Mele, we're a little off by one here, because I have to include zero, because we know that that's a base case, in our edition
1:03:18
of this problem. That being said, there are roughly n choices for the first number, node, and n choices for the second number in the node. And along with that, we know that we're not gonna have to travel through many duplicate sub trees, because we memorize them away. And so I think what I can say here is the total number of nodes you can possibly have is m times n, and I'll be the number of like distinct nodes, right? Because I have m choices
1:03:41
for the first number in the node and n choices for the second number. I know that I'm going to really minimize any duplicate exploration through the memo object. So the really the implication here is we started out with our brute force recursive implementation, which looked like it was exponential in the time, right, it was two to the n plus m time. And then by memorizing this function, we were able to bring it down to n m times n, time
1:04:04
complexity, which is much faster. Notice that the space complexity stays here, which is really fine, because n plus m is some sort of a multi linear function. Cool. So there, we have our nice optimal solution for this grid traveler problem. So key thing I want you to take away from this one is, although the initial narrative and the problem made it seem, you know, pretty specific, and pretty different from a previous dynamic programming
1:04:28
problem, like Fibonacci, was really the same sort of story, the most important thing that we're going to sort of leverage throughout in this lesson that we leverage twice already is try to think about your recursive functions in terms of a tree, right, I get the most information out of the tree. And then from there, I can use that tree to not only implement a brute force, but to also recognize, hey, where can I optimize this brute force, that way you can reach for the optimal solution.
1:04:51
Alright, so we've gone over two different problems together, and hopefully we're starting to notice how we tackled them in similar ways. I think it's about Tammy gave herself some guidelines for solving dynamic programming problems using a memoization strategy. So we'll call this our memorization recipe. And there are three different ways you can go about learning this topic of memorization. And you might have different recommendations.
1:05:13
This is just my particular recommendation. So I think the most important thing to establish if you want to, you know, solve some dynamic programming problem using memoization, is to stick to to like high level steps, we definitely need to at first just have a solution that's recursive. So just make it work could be slow, that's okay. And after that, we make it efficient. I think this is where a lot of students sort of try to take on too much at once. They try
1:05:37
to just solve it quickly all in one go. Right? To me, it should be a very separate process, right? First, I look for correctness in my solution. And then once I have correctness, then I look for efficiency in my solution. So when we go through step one, if I just want to get a working solution, then I have to start visualizing these problems as trees in dynamic programming problems, the gist of them are that we have some large problem
1:06:03
that I can break down into smaller instances of the same problem. So when I visualize it as a tree, what I'm looking to do is figure out all right, in the nodes of the tree, that should represent a problem. And when I draw an edge between nodes, that should be shrinking the size of the problem. And depending on you know how your problem is stated, you'll have to figure out that logic, right? In the case of our Fibonacci, it was as simple as
1:06:26
we know, we can decrement our values of n. But in the case of our grid traveler, what we had to do was travel rightward or downward. And once we do that, you want to implement that tree using recursion. What's great about a tree is it's already a recursive structure. Right? So how do you start to translate that kind of tree visualization to some recursive code? Well, you think about the leaves of that tree as your base case, right? Lately,
1:06:52
for us, it's been about some small numbers, right? So like a grid of size one, or it could also be in the case of Fibonacci, just our initial seed values of n equals one, and n equals two. Now, once you have that baseline recursion, that's going to be your brute force solution. And so you'll want to test it. To me this testing step is really important, right? So if you pass inputs into your brute force recursion, it should give correct answers.
1:07:18
Although possibly for large inputs, it may take a long time, right? To me, there's a big difference between code that is slow, and code that is wrong, right. So here, we should give back valid results, although maybe our code is a little slow. Once we have our working brute force solution, making it efficient using memorization is a very, very canned scenario. All we do is start by adding a memo object into the mix. So this memo object needs
1:07:42
to have keys which represent arguments to our function. And the values of that object represent the return values for those function calls. We know that in our functions, a unique set of arguments should give me a particular result. So we're just having that sort of mapping inside of an object, you need to make sure that this object is shared among all of your recursive calls. One way you can do that is to pass them along as arguments. And
1:08:08
lately, I've been doing that by giving myself a default empty object at the top of each of my recursive calls right through my top level call. And once we do that, we need to add a new base case into our code. So I'm not going to remove any of the old base cases, from my brute force solution to me, I'm just adding a new base case that captures the memo. In other words, if my arguments are in the memo object as a key, then I'll return the
1:08:35
stored value, I refer to that as like my memo fetching logic, right? Looking up some stored value in my memo. And beyond that, the only thing we need to do is implement our memo storing logic. And it's as simple as going to exactly where we had our return values in our function. And then we just make sure that we add those return values into our memo object before returning, right, so I always look to the exact return expression, and just
1:09:03
write some code around it, right storing that result into another mental object before I return it, right? Step two is actually very, very easy to implement, meaning it's very easy to memorize a brute force solution, it's really coming up with the brute force in the first place, that kind of feels more difficult. So as you're learning and practicing memorization for these dynamic programming problems, I highly, highly recommend you stay very methodical,
1:09:29
and follow these steps, right? Don't try to efficiently implement an algorithm from the get go get a brute force working solution with recursion, and then implement it using memoization. Afterwards, right. And as you get more practice with this technique, soon, you'll be able to do everything all in one swoop, but I don't recommend that until you've definitely finished this course. So we'll be sure to follow these rules for falling problems. Alright, so I think it's
1:09:58
tempting increase a difficulty and we're going to know Their dynamic programming problem. So let's work on this can some function, what I need to do here is take in a target some as an argument, as well as an array of numbers by function needs to return a Boolean. So true or false, indicating whether or not it is possible to generate the target some using some numbers from the array. And along with that, we have some constraints here, we can
1:10:18
totally use an element of the array as many times as we want. And we can also assume that all input numbers, so the target sum as well as the numbers of the array are non negative. So let's try to understand what this question is asking. Let's say I gave you this example case. So it looks like our targets, I'm a seven, and the array of numbers is 534, and seven, here, the response should be true because it is possible to generate seven, by adding
1:10:41
some amount of numbers from the array, one way you can generate seven is by just doing three plus four, another way would actually be to just take the loan seven, because seven is actually a member of the array. So it's definitely possible to generate seven using, you know, some amount of numbers from the array. So that's why we return true. Let's see, I gave you another example. Let's say I gave you a target sum of seven again, but
1:11:04
I gave you a different array of just two and four, this is actually going to return false, because there is no possible way that combinations of two and four can actually sum to seven. Cool. So that's really what the question is asking. Now let's try to think about how we can frame this problem of recursively. Right? Hopefully, you've already gathered in your mind. If we have a smaller amount of targets some, then they'll tend to be a smaller, easier
1:11:27
problem than a larger number for targets. All right, so let's start to think about the recursive structure. For the first example, we know in the long run, we should be able to derive the answer true from the string that we make. So like, we always say, we should encode the arguments to our function into the nodes of our drawing. That being said, since in the problem, they told us that we can reuse an element of the numbers array
1:11:51
as many times as we need, I'm just going to omit that from the node drunk, because basically, every node every function call is going to receive the same array. So I'll just list the target sum in every node. So I start with seven, and I have to think about how I can transition to other nodes, right? How can I shrink the size of this problem? Well, I know that I only have, you know, four options I can take right have an option for every
1:12:14
element of the array. So basically, if I'm at this seven node top level, I can branch to some children, and sort of the rule for my transition is you can either take a five, take a three, take a four, take a seven. And if I actually take you know those elements as a choice, they are going to decrease my current target sum. In other words, seven minus five is two, seven minus three is four, seven minus four is three. And of course,
1:12:39
seven minus seven is zero. So notice, we have a very particular rule from traveling from a parent node to some child, I can just carry over this pattern. However, we have to watch out right, so let's say I tried to flesh out this note where my target sum is two, if I look at the options I have, right, I still have the options of 534, and seven, however, none of them are really compatible with this target sum of two, right, what I don't want
1:13:02
to do is take any of these choices, because that would kind of give me a negative target sum. So I can't really flesh out this note two anymore. That is there are no valid options for this node. However, some of these other nodes like this for to have valid options. So what I can do is take a three or take a four, and of course, I get a one and zero respectively. And I'll also do this for the three over here, right? For this three node,
1:13:26
I can only take a minus three as a choice. Cool. If I look at all of the nodes that I have, now, I like the leaf level, it looks like they all sort of bottom out at a base case, that is there is no further choices we can take. And I also noticed that some of my nodes have a zero in them, if I look at the notes that have a zero in them, they actually are a really nice base case, because I basically have found that I can generate
1:13:51
to the original target sum right away, you can kind of understand the base case, when the target sum is zero is you can always generate a sum of zero by taking no elements from the array, right? So these zero nodes are trivially solved. And to me, they should return a true backup to their parent, right. And it's sort of on the flip side for all of my nodes that are not zero. And they also can't break down into any further nodes. Those return false,
1:14:18
right? Because they kind of have a leftover. And I know there are no possible options I can take to reduce that further. So all of these other nodes should return false to their parent. And remember what this question is asking, right? It's really asking, Hey, is it possible at all to generate the original target sum? And so the logic is when these values these Boolean values return to their parent, the parent should just check if at
1:14:41
least one of them is true. And if at least one of them is true, then that parent should also return true. And if I look at this for note, have a tree above it, and that sort of answers the question, Hey, can I generate a sum of four using elements of the array and you totally can because if you look at the elements of the array, there is exactly one for so I can just take that into my son. So I'll be sure to bubble up, you know all
1:15:05
these Boolean values to their parent. And again at the parent will just make sure that at least one of the values that gets back is true. And so if at least one of them is true, then the parent itself will also return true. So very reminiscent of some like Fibonacci bubbling up pattern as well as our grid traveller, except now we're kind of adapting this for some boolean data, but it's really the same structural understanding I have. Cool. So
1:15:31
that was an example where we said true, right, there is a way to generate the sum. Let's look at another example. Right? How do we know the flip side. So if we have this example, right, seven, and an array of two, four, in the long run, that's gonna return false, right, there's no possible way you can generate that target sum of seven. So the tree for this example would look like this. So this is a full tree. Notice that all of the leaves get
1:15:54
as low as one, but they can't be broken down any further. Like we just said, in our last sketch all of these ones, since they can't be broken down any further, and they haven't reached zero, they're going to return a false up to the parent. And I know that if I bubble up all these false values, of course, a top level call will also return false. Right? So it looks like a key insight we have for this problem is, if we find at least, you
1:16:18
know, one base case that returns true, I know that I can sort of stop early and just return true all the way up to my parent, because they're not really asking like, how many ways can you generate the target sum? They're just asking, Hey, yes or no, can you generate the target sum at all. So that's gonna be a really nice way to implement this code. I think we're ready to jump right into the code. So let's do it. Okay, so let's go ahead and implement
1:16:42
this can sum function. So since we're going to solve it recursively, I think a good starting place, as always, is to maybe handle some of the base cases. So when we drew up the tree, I noticed that one of our base cases was when the target sum reaches the value zero, right? If our target sum is zero, then we have like, basically trivially solved the problem, because you can definitely always generate the target sum of zero by taking
1:17:06
no numbers from the array, right? So I'm going to return true. If ever I reach a zero, then Apart from that, I think let's go ahead and work on the recursive scenario. So I know that I need to establish some logic where I make a recursive call or a branch for every element of the numbers array. So what I'll do is I'll iterate through that array of numbers. So I'll use some for let of syntax we'll say let num of the numbers, right. So if you're
1:17:32
unfamiliar with the syntax, all it does is iterate through every element of the array. So for example, let's say I just called the first example for can sum of seven, and an array of two, three, if I just console dot log, the num, I'm just going to see the elements printed out of two, three, right, so let's give this a quick spot check. Nice, so just iterating through every number of the array, no tricks here. But now that I have that number,
1:17:56
I need the branching logic. So remember, the logic we use for transitioning from one node of the tree to the next, what we did was subtract our current choice of number from the target sum, and they basically gave us like the new target sum. So I'm going to express that and maybe some variable, so I'll say, Alright, I'm going to generate the remainder by calculating the difference between the target sum and the number, right, so I'm just subtracting
1:18:21
the number from my target sum, that gives me my new remainder, which becomes a target sum. Right? So at this point, I think I need to call recursively on can some of our pass in this remaining quantity? It doesn't need a second argument, still, I'm still gonna pass in the same exact numbers array. So I'll still pass in numbers unchanged. I think that you know, the fact that we pass in the same exact numbers, right, it's pretty consistent with the way they stated the problem,
1:18:46
because we can totally reuse the numbers of the array as many times as we like. Cool. So now that I'm using our function, again, I'm making the recursive call, I want to think about what this call will return. I know at any point in time, my can sum function is going to return Boolean. And what's great about boolean data is there's only two possibilities, right, either true or false. So I think, based on what we said about the tree was, if this
1:19:11
call, if that returns true, then I can just ultimately respond with a true right now. So I'll write it like this. So this is saying, All right, if we figure out that it is possible to generate the remainder now using numbers of the array, then I can return true for this larger problem of target some, right? So if I find at least one way that works out, then I'm going to do an early return true. And the really important pattern here is we don't
1:19:41
want to write the LS and then return false. Instead, we'll want to return false after the for loop. And so here's the reason why you want to return false after the for loop. I only know that after I attempted you know all possibilities and I found that none of them worked out Can I actually say that it is impossible to generate the target some Right, so I need to make sure that this for loop tries all possibilities of number. Before
1:20:05
I can say false, the target sum cannot be generated. That being said, there's one thing we should add to our code. So if you look at line six, all right, I'm subtracting our choice of num from the target sum. And that means that sometimes the remainder might become negative. So remembering our tree structure, we made sure to sort of return a false whenever we had a sum note, I didn't do any branching. To kind of account for that I can kind of
1:20:30
bake that into another base case. But this time, make sure it doesn't return true. So I'll say, you know, if my target sum is negative, if it's less than zero, then you've gone too far. And you can just return false. Here, it's safe to just automatically return false if your target sum hits something less than zero, because you've gone too far. And there's really nothing else you can add from the numbers array to ever fix that negative target sum.
1:20:56
Remember, they told us in the problem, that your numbers are always going to be provided as positive numbers or just zero, right? So let's go ahead and give this a go. So I'll try all of these examples. And we'll see what we get. So I expect a true true false, true, false. Cool, so looks like a few of them are working right, it looks like the first four are working totally fine. But looks like on that last example, my program still running.
1:21:27
And if you notice, I chose a pretty large value for em. So kind of like we expect this solution has correctness. But it possibly lacks some efficiency, it looks like it just finished, the definitely took way too long. And so it's a very interesting example of a slow input to can some, because for one, the length of the array is pretty sure I only gave two elements here. But it seems like this number as a target sum really affected
1:21:54
the runtime. So we'll do, let's head back to the drawing board, and talk about the complexity of this baseline solution. Alright, so we implemented the brute force for our khamsum. But obviously, now we want to make it a little faster. But before we kind of just jump into memorizing the solution, let's at least describe the complexity of our current brute force. So let's try to visualize this example. So I have a target sum of eight. And my choices
1:22:18
for my numbers are two, three and five. In the long run, they should return true, the visual for the full tree would look something like this, notice that it's fairly large tree of forbs and relatively small inputs, right, I only have a target sum of eight, and only three choices. So let's try to describe the complexity of this, I'll sort of generalize the shape of it, get rid of those numbers. So this is the overall shape of the tree.
1:22:40
And I know I want to describe my complexity in terms of the input to my function, this function has two inputs to the right, I'll say that M is the size of the target sum, and n is the length of the array I'm given, I know that both of these arguments definitely have an effect on the dimensions of this tree. So like we did in all of our other examples, I'll start by maybe analyzing the height of this tree, that is a what would be the maximal
1:23:03
distance from the top level call to a base case, or in the structure of the tree, what is the maximal distance from the root of the tree to the farthest leaf. So if you sort of imagine that, we have m as the root of the tree, imagine that along the left hand path, we just did a minus one all the way down, right? So we kept taking a minus one, right? In the worst case, maybe there's a minus one present in our a numbers
1:23:27
array. In the worst case, the distance from the root to a base case would be exactly m, because you have to subtract one m times, right. So I can basically say that the height of this tree is M. And it kind of like we said in our other problems, that means that the number of levels is m right. So now that I've identified the height of this tree, the move is now to identify the branching factor. That is, how does the number of nodes change
1:23:51
from one level to the next. Remember that initially, we described this particular tree example is having numbers array length of three. And you'll notice that the maximum branching factor is exactly three or in general, N, right? because n is the length of the array. So for example, if I had three numbers in the array, then a node would have at most three children, right? Cuz you have three options to take. We've seen this pattern before
1:24:15
I have n levels, and from one level to the next, I would multiply the number of nodes by n, right? This is the same thing as saying, Hey, we take n and multiply it by itself, m times. And this would definitely give us an exponential complexity, right in particular, and to the M time complexity, like we always say another great thing about this type of diagram is we can also derive the space complexity, right? So what would be the space used by
1:24:40
the call stack, it would really just be the height of the tree, which we already described as M. So overall, our brute force is looking at an end to the M time complexity, and M space complexity. So now that we actually have you know those concrete numbers for our complexity, let's go ahead and focus on how you can truly improve this So here's again, the drawing for this particular example. It's a fairly large one. And typically, you know,
1:25:05
when you're trying to notice where there is room to be optimized, you might have to give yourself a sufficiently large example to see these scenarios. So in this example, I do have overlapping subproblems. And in the context of my tree, that means I have duplicate sub trees. So I can look at possibly this subtree rooted at three, notice that the root of that subtree is trying to answer the question, Hey, can I generate a target sum of three
1:25:30
using the array? And of course, once you find that answer, that answer is never going to change for your target sum of three, right? So I know that all three of these sub trees are trying to ask the same problem. And so what I'll do is I'll just cache those results in my memo object like we always do. Let's go ahead and work on that. All right, welcome back to my code editor. And same stuff, different days. Let's go ahead and minimalize. This
1:25:56
can sum function, right. Once we've established the brute force through the recursion, then memorization is pretty formulaic. Right? Alright. So we'll start by just baking in our memo object like we usually do. So if someone calls our function without a third argument that is like a top level call, we'll be sure to give them a new object. And I'll, before I forget, be sure to pass down this memo object, I'm going to make sure that every top level
1:26:20
call and it's recursive tree shares the same memo object. But now I need to figure out what what should I use to key into the memo object. So here I have two arguments of my original function are I have targets summon numbers, what I want to do is try to notice, you know, which of these arguments is actually going to directly impact the return value. So I know that through the recursive calls like this call over here, the numbers argument
1:26:46
doesn't change. And so if it doesn't change, then right now, it doesn't really affect other return value. So I'd be okay to just use the target sum as the key into this memo. So we'll go ahead and do that. So I'll check if my target sum is in the memo, that I've seen that sub problem before, so I can just return the stored value. Cool. And now I have my, you know, memo fetching logic. But now I need to actually store things in the memo. And
1:27:17
the trick is, what I want to do is look at all of the return values that were not base cases, and I need to now store them in my memo. So I have to return values here, right, these two lines, lines, 10 and 14. And so I need to store data into the memo for both of those lines, it's as simple as quite literally going into your memo using your key, so target some, and then assigning the value we just returned. So I'll just write it like this. And this is going to be sort of a hard and fast rule,
1:27:47
you can always use our for a memorizing a brute force recursive function, right. So I'm just going to take exactly the lines or the expressions that I returned in the recursive scenarios. And now just store them in the memo. Cool. So let's go ahead and give this a shot, this code is looking pretty good. And remember before this last call with an input of target, some 300 took notice will be long. But I think now when I give this
1:28:13
a shot, right, it finishes really quick. So this is going to be a nice optimized solution for cancer. Really, most of the work of this problem was done in the brute force. And then afterwards, it's really just a minor adjustment to make it efficient. So to wrap up this problem, let's go ahead back to the drawing board and talk about the improved complexity. So we definitely memorize the heck out of that code. But let's recap by just understanding what
1:28:38
the new complexity is. So again, we're saying that M is the target sum, and n is the length of the array. Initially, we said that our brute force solution had an end to the M time complexity, which is exponential. And actually, once we memorized it, we really cut down on that complexity, we brought it down to n m times n type complexity. And so here we say that the memo is complexity is now m times n, because of the memo object, right? We know
1:29:02
that the value of the nodes in the tree are just going to be values up to m or their m different possible values we can have in a node. However, it now since we are able to cache values or cache results inside of the memo object, I'm never gonna have to re explore a subtree before M. That being said, I select the branch and times for each of those nodes, right. So overall, I have m times n nodes. So hopefully that can some problem made some sense, because we want to do now is actually
1:29:33
carryover a lot of that knowledge to solve this new Howsam problem. So this problem is very similar, it still asks us to take in some target some an array of numbers, but this time around, we want to do is return an array containing a combination that adds up to exactly the target sum. And if there's not any combination that actually leads to the target some, then I should just return null. Along with that, if there are many possible
1:29:55
combinations that can reach the target some that that can return any of those. So you probably Already recognizing that this house some problem is very similar in logical structure to the can some problem right? instead of returning a Boolean instead now I want to return exactly the combination of elements of the numbers array that leads to my target sum, so it's a little more involved. That being said, let's take a look at some examples
1:30:18
to make sure we're on the same page. So let's say someone asked us to calculate how some and our target was seven, and our array of numbers are 534, and seven. So there are actually a few different combinations that can give you your target sum of seven. One way would be to take three plus four, that's one possible answer, another possible answer would just be returning an array of seven. So no matter which combination array you return, it'll
1:30:39
be considered correct in either scenario. Let's say I gave you another example, where your target sum was eight, and your choice of numbers were two, three and five. One possible solution for a combination is two plus two plus two plus two, right? So I returned that in an array, another combination would be just three plus five, notice that no matter what we're always looking to get back in array, if it is possible that our target sum can
1:31:03
be generated. But let's look at the flip side. Let's say that we were given this input, so I have a target sum of seven, and my array of numbers is just two and four, the first thing we notice is it is not possible to actually generate the target sum of seven. Like they said, the problem in this scenario, what you want to do is return Nome sort of symbolize that, hey, it's not possible to generate any combination that leads to the target sum.
1:31:24
All right, I think it's important that we think about one more scenario. So let's say that I was given a target sum of zero. And we were given really any array of numbers. In this case, I just gave us one, two, and three, we already know that in our previous problem, we had to return a Boolean result, we use the target sum of zero as a base case. And so what I want to think about now is how is the target sum of zero just trivially solved?
1:31:46
Well, if I want to know the combination that sums to zero, and that's really just the empty combination, right. So I think the logical result here is to return an empty array, when your target sum is zero. Remember that an array represents a combination. And if I have an empty array, that means I take no elements into my combination, right? If I summed up all the elements in that empty array, it would indeed have a sum of zero. So that's going
1:32:09
to be a really important facet that we need to encode into our logical tree that we draw next, as well as our code, right. So let's take a look at how we can structure the tree and try to take a step toward really understanding how we can implement it in some code. So let's say we're stepping through this particular example of target sum of seven, as well as an array of 534, and seven. So the full tree and really the same tree that we drew last
1:32:31
time would look something like this. from the get go, I see that I have some scenarios or some nodes where I reach zero, which means that it's definitely possible to generate the target sum. That being said, How can I get back a valid result, right, so I need to return an array. So you sort of reframe this problem in that, all right, all of these base cases that have a target sum of zero, they are trivially solved because they are
1:32:55
combination would just be the empty array. Right. So for now, I'll just kind of trace through how one of these base cases would return. So I know that this particular zero is going to return an empty array. And like we always say, when it returns, it's really returning that information to its parent, right. So this array sort of bubbles up to its parent. And now what I want to do is actually manipulate this return value, I want to add
1:33:17
something to it. So I want to really put the number that brought me to that zero in the first place. And that would really be the choice of four. So notice along the edge, I have them labeled with a minus four, meaning that, hey, I took a choice of four. And I want to actually add that choice into the current array. So I'll just really push it into the right, of course, I actually don't need a negative sign that was just for the
1:33:38
sake of understanding the math here. But now that my call to how some of four is returning an array of four, that array bubbles up to its parent. And of course, now I need to push that edge that I took, which would be that three, so that three gets pushed to the rear as well. And if I look at what I'm seeing right now, it looks like above the seven, we have an array of four, three, which makes sense, because you can totally generate a
1:34:03
target sum of seven by doing four plus three, awesome. So four comma three would be a valid answer in this particular problem. But like they said, you could return really any valid combination if one exists. So let's say we retrace through this far right base case, we know that this zero is going to return an empty array, that empty array will be returned to the parent. But we also have to add the value according to the edge, right? So I would
1:34:28
press seven in this array. And that makes sense because I could generate the target sum of seven by just summing up a loan seven. So that's still good to go. So I'm feeling pretty good about how we can return a valid combination if one exists about let's say, there are some options that we take that don't work out. So for example, let's say we explored this node first, right? This was the first base case we had and logically in the space
1:34:51
of our code, it really would be right. So I know that this node can't really branch out any further. So it's sort of a dead end. This is a node that should work Turn no meaning that, hey, there is no way I can generate a target sum of two using elements in the array. Or if you look at the elements of the array, they're all too big, right? So I know that this base case is going to return null. But along with that, if you look at the next
1:35:15
base case, we would hit it would be this one, which also returns Now, if you look at the next base case, to the right, that's actually an affirmative one that should return an empty array. So it's kind of reasoned out how these return values should be considered at their parents. So I know that both of these values, but to the left of the node four would return, right, so it kind of bubbles up a little bit. But for the array on the right hand side,
1:35:37
I would also have to push the edge that I took, which was a four in this scenario. So now I'm sort of comparing you know, the nollan, this four, or really, I'm comparing all of the branches that I take from a node. And if at least one of the branches gives me back an array that I know that it's possible, right? So basically, in this scenario, the array of four actually wins out over the null, right, I know it's possible to generate a four. And
1:36:03
I'll just continue this process, right, now I can return these two values to its parent. So let's I'm considering them at seven. In the same way, I would have to add the edge I took, which would be a three on this array. And then from there, I know the array would always override the null, right? So I could just ultimately return this four comma three. And a really nice pattern in this code is, as soon as we find a winning path through
1:36:27
the tree, or that is we find a combination that creates a target sum, we can actually return early because we don't need to really travel through the rest of this tree. We don't need to explore any other options because they're happy with at least one combination. Right? Awesome. So again, to recap, the punchline is for this tree, I have the information for a combination, encoded as a path through edges of this tree, right, so I've looked at this
1:36:51
path I have highlighted in yellow, I see that I took a three followed by four. And that eventually led to a zero. So I know that one valid combination would be four comma three. All right, at this point, I'm feeling pretty good. Let's go ahead and work on the code for this now. All right, here we are back in my code editor, let's work on solving the house implementation. So the codes going to be pretty similar to the cancer problem, it's
1:37:13
the really the whole point, we're just kind of going to finesse the return date over here, we're gonna have a very similar base case, like we said, in the tree diagram, whenever we have a target sum, that's zero, we have trivially solved the problem, because I could just return an empty array. And a similar way, what we can do is also have a separate base case, if our target sum ever reaches a negative quantity, then I'll just return
1:37:34
null. That's because it's never possible to generate a negative target sum, right? Remember, in this problem, the array of numbers is only going to be positive ones. Cool. We ended up writing very similar base cases for our last problem, except now instead of returning true, we return an empty array. And instead of returning false, we return nil. Nice. So let's go ahead and get the branching logic. Right, how do I want to make my recursive
1:37:57
calls, I'm going to need to make a recursive call for every element of the numbers array. So I'll say, let num of numbers, we'll just iterate through every number of this array. And I'll go ahead and do the same logic as last time. So I'll subtract the number from my target sum, they'll give me my remainder, right? So remainder equals target sum minus mine number. Cool. So this remainder is now what I want to find the combination for, right?
1:38:23
So here, I would make my recursive call. So how some pass in the remainder. And the second argument will stay exactly the same. I'm going to pass along the same exact numbers array. I don't need to remove anything from the numbers, right? Because they tell us in the problem that we can reuse the elements however we see fit, right. Cool. So now I need to really think about what type how some returns. So this problem is interesting, because we basically have two different types, right,
1:38:47
we could get back in array of some elements, if it is possible to generate the remainder, or we can get back know, when it's not possible to generate the remainder. I think no matter what I get back, I'm just going to save into a variable. So I'll say console, this is the result for the remainder. I'll call it remainder result. Cool. So I know that in the context of like how I thought about this logic in terms of the tree, I wanted to basically do
1:39:14
an early return if I found a valid combination. And so I'll go ahead and check you know, if the remainder result is not No. So the implication if I enter this if statement, that means that it is possible to generate the remainder. And so what I can do is just return early and I can return of basically almost the same remainder is also the same array. However, I need to make sure I include the element that I took recall from the diagram, whenever
1:39:44
we had a recursive call that returned in array, the parent had to also add the number that it took transition to that recursive call in the first place, right. So in the context of the tree, I had to put the labels of the edges into the array here. means I have to put the num into this array. So some syntax I can use for that. So use some spread operator. So I can copy all the elements of the remainder result into this new array. But I'll also
1:40:12
add on the number I just took, right. So all I'm doing in this return line is, I'm returning basically the same array that I get back from my recursive call, with the number added to the end of it. Let's say you're unfamiliar with this syntax, I can preview it really quick. It's pretty neat. Let's hop into the, you know, repple. So let's say I had some array, let's say it was this array of just a, b, c, sort of an isolated example, you
1:40:37
can use the spread operator, which is the three dots here to like unpack an array. And you can sort of say like, new array equals bracket. So this gives me a new literal array, I can spread out the elements of the old R, right? So if I do that, the new array just has all of those same elements, vi, capitalize that and properly, cool, we can extend that syntax, right. So I still have that array of ABC. Let's say I had another variable,
1:41:03
we'll call it other array, what I can do is create a new literal array, copy all the elements from our using the spread operator. And then I can comma, separate any additional things I want to add while I'm here. So let's say I added a z. So if I look at my other array, now, it contains ABC, and also this new element z. So it's all I'm doing on this slide, right? I'm returning the same combination, that my recursive call gives back with the number
1:41:30
that I took are added to the end of it. Cool. So what's really nice about this code is it's very reminiscent to our previous code, because we have an early return. So if I find at least one way, to generate the target sum, I can just go ahead and return that first way that I found, right, they say we can return any valid combination here. But let's say this for loop finished, and we never found a valid way to generate the target sum, then after
1:41:53
the for loop, you can just return null, because it's not possible not to generate the target sum, apparently. Cool. So this code is looking pretty good. I think let's let's give it a shot. It goes without saying no, sometimes the remainder right will become negative. But we already handled that with this nice base case, right. So let's test this code. So I already have some example outputs over here. So looks like our first few examples
1:42:23
are working. Obviously, our last one seems to take quite a long time. So I'll just kill this program early. But before we talk about how to optimize for this larger example over here, if you look at these other examples, what I can see is this array of 322 does add to seven. So that's looking good. This array of four, three, also adds to seven. So that's good. We already saw that this example of seven and two for now, that's your return
1:42:49
No, because it's not possible generate that sum. And it looks like the array for the eight example is also good to go. So notice here, there are also some other arrays that we could have returned and would still be considered valid output, the exact combinations that we get back are really just dictated by the order that we happen to iterate in the array. So for example, let's say I switch things around here, like I did 352, it's really the
1:43:12
same array, just in a different order, we'll probably get a different answer for that particular one, right? So I'll run this now, notice I get 233. But either case, that still sums to eight, so we're totally good to go. Awesome. They bring this back to the original code. And yeah, it seems that now the limiting factor seems to be the speed of our solution, right? We've been here before. And so let's go ahead and talk about the complexity of it. So we know that the
1:43:40
time complexity for this is almost identical to what we did in the cancer problem, which is conveniently over here. But sort of refresh. By now you recognize that all right, the time complexity should be described in terms of like the recursive tree, let's let's lay down the foundation. And we already know that M, we're going to call the target sum. And let's also say that n is the numbers dot length. Cool. And so if I think about the number of
1:44:07
recursive calls that I'm going to make, it's really the same as last time, right? So I'm going to say that, hey, the time of this function seems to be Oh, and I have an exponential, the base of the exponent is the branching factor, which is the length of the array. And then the depth of the tree would be the exponent, which is just m, right. So this was the same time complexity as last time for a brute force writes M to the M power.
1:44:33
However, it looks like we have some additional time that we consume in this function really coming from this expression, right. So if I look at line nine, in particular, this line creates a copy of an array. So that will actually take sort of a linear number of steps to copy over every element of an array right. So I will have to consider the cost of this operation. It sort of under the hood like iterates through the remaining result, I know that the maximal
1:45:03
length of the remainder result I can get back will be at most m, right? Remember that remainder result in the worst case is going to be in array, the longest that array could be is exactly the target sum, right? Imagine that we had the most simple, you know, sort of a combination to generate the target sum. If it was just a bunch of ones, right, my target sum was 50. And I had an array filled with one, then I can just do one plus one
1:45:28
plus one plus 150 times to generate the target sum. So in the worst case, this copying operation will take m steps, I need to do that for every recursive call. And so if I have this many number of recursive calls, in addition to that, I do an M operation, you just multiply that M, right. So the time complexity for this brute force so far, is n to the n power times M. Really, the thing we want to optimize away is this exponential part, right? So I
1:45:57
really want to focus in on that. But while we're here, let's go ahead and talk about the space of this brute force. So the space, there are things to consider the terms of the stack space, it's going to be the same as last time, so it's going to be o of m. But think about any other space I use up I guess you should also consider the array that you return back, whoever we know that we're going to return back like the first array
1:46:20
that we find all the way back up to the top level call. And the combined length of all of those arrays that we return is really just going to be in worst case, M. Right. So I would still say that the space complexity for this function is just m right now. Cool. Obviously, let's work on optimizing this time complexity. So this was the brute force. So brute force. And you guessed it, and there is definitely some people get some problems
1:46:47
in this brute force. So we'll just memorize it away. So very formulaic stuff, most of the work is always the brute force. So I'll start with my empty mental object. And like we always say, we'll use the target sum as our key. So if I've seen the target sum before, that is if it's in the memo, then I'll return what I have stored in the Mo. And at this point, what I want to do is make sure I pass along the same memo object to all of the recursive
1:47:14
calls. That way, they can benefit from any information or any sub problems that I worked on over here, right in this stack frame. Cool. At this point, I need to make sure that I take all of the return lines that I had before, and I store them in the memo, right? So the trick here is I can say, memo of target. So I'm going to save that array. So notice that now the values in the array, or sorry, the values in the memo object are going to be
1:47:43
arrays, because that's the return value of this. It's either going to be an array or not right? So I'm just going to complete this return value by returning what I just put in the memo. And in a similar way, I also want to memorize this late return. So we'll also be memo of target sum equals No, I can just still return No. Cool. So with that change, right, it's very, very straightforward change. Let's see how this does. Now. I know that for this last
1:48:14
example of how some 300, it is not possible to generate the sum of 300 using just sevens and fourteens. So should we get an all for that one. So let's give that a shot. Nice. And there, we have a really quick running a know of that very last example. So we definitely had an effect on the runtime here. Let's talk about how we changed up the complexity of this code. So that was a brute force. Let's talk about the memoized version. So it's good
1:48:42
with the time over here. So we know that in terms of the time complexity from the number of recursive calls that we make, it's the same story as our last problem, right? We just have to consider any other time operations, which would still be this array copying. So but in just terms of the recursive calls that we make, it's going to be n times m, recursive calls. And then in each recursive call, I need to do this copying pattern, right copying
1:49:08
over the contents of an array, and the array will be at most m elements long. Alright, so if I have this many recursive calls, and each recursive call needs to make an M length operation, now I just multiplied by another m term. So right now this looks like n times m times m, which is the same as n times m squared. And I'll talk about the space complexity. So the space complexity will be at least as big as our brute force, so it's going to be
1:49:38
at least o of M, above, now we have to consider all the space we use up in the memo object. So I think about the keys of this memo object, the keys are just going to be all unique values of target sum, right? Because I just literally use target sum as a key on all these lines, right? But then everything about the value or the values are going to be Pretty chunky now, because sometimes of value but in the object is going to be an array. And I already
1:50:07
said that the maximal length of any of these arrays that I returned is going to be of length M. Right. So to me, it's now the case that your space complexity comes from mostly your mental object, which is going to be of size, m times m, right, because you have m keys. And each key has a value, which is, at worst going to be an array of M elements. So it's m times m, which is m squared. Cool. Notice that we definitely cut down on the brute force
1:50:36
implementation, especially in terms of the time complexity, obviously, there was a little trade off that we made here. But now we're able to run our house and function in a reasonable amount of time. So to wrap up this problem, let's go ahead and hop back into the drawing board. Alright, now that we coded the house and prom, let's wrap it up by actually analyzing the complexity of it. So recall that for our house, some problem, we have multiple arguments,
1:50:59
right, so I need to describe them. So I'll say that m is my target sum, and n is the length of the array. Remember that the array contains the choices we can take. And our baseline solution, that is our brute force recursion had an exponential time complexity, right? It was kind of in the form of n to the n power times M. And after we actually optimize it using the memorization strategy, we actually reduced it from exponential down
1:51:22
to a polynomial time complexity. In particular, our new time complexity was n times m squared. So really important fact about our memoized have complexities, it is no longer exponential. Please recall that when we have m squared, that is not exponential, because the exponent is a constant number. Cool. If I look at the the space complexity for this, I had to actually pay a little more cost in terms of the space because of the memoized object. But that space
1:51:50
complexity we use up is still not exponential, right? Still a polynomial or quadratic complexity. So I'm still satisfied with it overall. So we definitely prefer this memo is complexity over the brute force. All right, that was the how some problem but now let's go over one more variation of it. In this problem, I'll still give you a target sum as well as an array of numbers to choose from. But this time, what you want to do is return an array containing the shortest combination
1:52:17
of numbers, that adds up to the target sum. And along with that, if there's any ties for the shortest combination, you can return any of those shortest ones. So from this description, you probably recognize that this is similar to our last few problems. But now they're asking for a little bit of an optimization, right? So I want the shortest sums, that means an array containing the least amount of numbers, but it still adds up to the target sum. So
1:52:39
we're really just going to add on top of our previous understanding, let's take a look at a few examples. So let's say I gave you this example. So here, my target is seven, and the numbers I choose from are 534, and seven. So there are a few different ways you can generate your target of seven, one way would be to do three plus four, that's one combination. But another way would be just take the seven because notice that seven is
1:52:59
actually a member of the array. And here I want to choose the smallest array, which would be just the lone seven. So that would be the expected result for this one. In a similar way, let's see, I gave you a target sum of eight. And your choice of numbers were two, three and five, there are plenty of ways to generate eight, you can do two plus two plus two plus two, or you can do two plus three plus three, or you can just do it three plus
1:53:22
five. And here, I want to return always the shortest combination, which would be the three plus five. So that would be the result over here. Cool. So we definitely have some awareness that Alright, this problem is similar in structure to our previous one where I need to sort of generate a way to make the target sum. But now I want to really specify the shortest array, right? So let's try to visualize this as a tree. Like always, let's say we're stepping
1:53:48
through this example, with the target sum of eight. So we know that the full tree would look like this. And we've seen this tree before. But now what we're trying to do is come up with a different process for the value your return, right, it's no longer going to be valid to just return the first way that I find to generate the target sum. Now I want the best way. So let's start coming up with the strategy for this. At this point, we know
1:54:08
that we can definitely implement some logic in our code where we return an array up our recursive calls, we did that in the last problem. So here, we'll sort of use some abstraction to assume some return values. So let's say that I'm bringing this problem down, my top level problem asked me what's the best way to generate eight. But I see that along that path, I have to find the sub solution for the best way to generate six. So let's say
1:54:31
we're rooted at this subtree. And we know that there are a few ways we can make six, right? If I look at this subtree rooted at six, there are two zero base cases downward, right? So if I look at the first one, I get this path, I know that my sub tree over here will be able to know that all right, one way to generate six would be two plus two plus two, right? We kind of implemented that logic in the last problem. But now what I also want
1:54:56
to do is consider any other paths in case they end up being shorter. Obviously, I know That this path of three 300 return upward. And now I have to kind of make the decision, you know, between these two options for generating six, I should just prefer the shorter one. So that means it's sort of two to two versus three, three. And obviously, the three, three wins because the array length is shorter. And if I pause right here, and I looked at
1:55:18
what the diagram is saying, it does make sense that above the six, we have three comma three, because that is the shortest way we can ever make a six, right, just three plus three. But now I can return this sub array to my parent. But if I do that, I should also include the value of the edge along that path, right? So I also included the two over here. Now this makes sense, because one way I can generate eight is three plus three plus two, right?
1:55:44
But we know that's not the optimal way. Let's say we step through this a little further, let's say we took the same sort of process for this other child of five. So I know that to generate five, there are three options according to the subject, right? Because I see three different leaves that are have zero inside of them. And so I know that for these paths, they would work out through their own sub arrays. And here, I really just want to
1:56:08
choose the shortest one, right? So obviously, the lone five wins out over here. So that'd be returned all the way up to that five node. But then that five node will return it to its parent, then, of course, I need to include the edge that connects the eight to the five, right? How did I transition to that five in the first place, so I go ahead and just add it in. And now the root node over here has a decision to make, which one does it prefer
1:56:30
between 332 or five, three, it'll just choose a shorter one. So the five three should win out over here. And I just need to continue this process for any other branches in my tree, right? I can't return early and this type of problem because I need to find the optimal way. And I can't be sure until I've tried every possibility. Cool. So it looks like our overall logic is we want to explore and find any ways to generate our
1:56:57
target sum. But then when we find a way that's shorter than our currently tracked way, we can just replace it, I'll continue that process through the entire tree. If I checked every possibility and keep replacing what I consider the shortest. By the end of us exploring every branch, we would have the absolute shortest. Alright, I think we're ready to hop into the code. Alright, programmers, welcome back to my text editor. Let's work on coding this
1:57:21
one out. So here I have some initial examples that we'll use to test our best sum function. I noticed for this last one, right, I get my initial target sum of 100. And the best way to do that is obviously just take a bunch of 20 fives, right for 20 fives. What else I want to bring our attention to is this third example over here. So my target sum is eight. And my choice of numbers are one, four, and five. The optimal answer here is four and
1:57:43
four, right? That is the shortest way to generate at a common mistake I see a lot of students make is sort of assume that the best way to generate a target sum always involves taking the largest choice of number as many times as we can, right? That is not true. If you took a five in your your sum, then you would have to take three ones in the long run, which is not going to work out to the shortest answer, right. So it's not the case that just taking
1:58:07
the biggest choice of number always yields the target sum in the shortest amount of numbers overall. So don't fall into that trap. Which means that we have to do the full tree exploration, right, we have to do that in exhaustive sort of search using our recursive code. So let's start with that base case, like we always do. So bring this a few times, but still right here. So if the target sum is zero, then I have trivially solved the problem. So I can
1:58:30
just return an empty array, right? That is the exact single combination and the shortest combination that can generate the target some cool along with that, let's handle that scenario, if our target sum goes too far downwards, if it's less than zero, so if the target sum is less than zero, I'll just return null, meaning that it's not possible to generate that target sum. And now we'll use our branching logic. So I'm going to iterate through all
1:58:53
choice of numbers will say for let num in numbers. And like we always do, I'll go ahead and create my remainder, which I know would be the difference between my target sum, and that choice of number. Right? So what I'm doing is I'm choosing the number that decreases my target sum. At this point, I would make my recursive call right with that remainder, passing in the same numbers array. But now I have to do some thinking, I know that all
1:59:18
right, best sum is either going to return to me a combination or an array, or it's going to return null, so I'm gonna have to kind of differentiate between the two. So over here, maybe I'll just save this as a result. I'll call this my remainder. Let's say combination. And if this remainder combination is not null, then it can do some other logic, right? So I'll say if the remainder combination is not equal to No, then do stuff. So if I enter
1:59:49
this if statement, then that means it is possible to generate the remainder. And exactly what remainder combination is, is an array containing the short This way, I can generate the remainder. Cool. So if I enter this if statement, then I also have a way to generate the full targets, right, I can just take the remainder combination, copy the elements over from it like we did last time. And also add on the choice of number I just took, right. So this would be now a
2:00:18
complete combination for target sum. So I'll just say that as a regular combination. Cool. So so far, this is very reminiscent to our last one. And we need to work in some more logic relevant for this problem, that is a very, very important characteristic that we needed to implement in the tree was, I need to sort of choose the shortest combination, RAMs, I'm going to need to work in that logic. So here's what we can do, I know that I need
2:00:46
to compare basically, all of my branches together, all of my recursive calls together, and pick out the shortest combination. So I know that this for loop is a piece of code that sort of iterates and attempts, all of my branches. And so outside of the for loop, I'm going to need some outer variable, I'll call it my shortest combination. And over time, I'll just keep updating this variable if I find a combination shorter than my current shortest
2:01:13
combination, right? So I'm gonna initialize this to null. And the reason is, imagine that we set up this shortest combination of variables, no. And then we iterate through the for loop. And there isn't even any way to generate the target sum. So this for a loop finishes, and shortest combination would still be no. And that'd be great to return, right? Because in this problem, they said, if it's still not possible to generate the target sum at all, you should still return null. So this
2:01:42
is a good initial default value for shortest combination. But now I need to do my update logic. So here on line 11, I've actually created a combination, that gives me the target sum. But now I need to check, right, so I'll say, if the combination is shorter, then the current shortest that I need to update it. So let's translate that into some code. Just use an if statement. And I'll start by checking if the combination I currently have, which is
2:02:11
an array, right? I check if that is less than in length, then the shortest combination variable. And really, it looks like shores combination, it starts as null. So I need to fix this code a little bit. But if I update it with a valid combination, then it's going to be an array, right? So I'm really checking the length of the arrays here. So what I want to do is assign my shortest combination with the combination that is now shorter,
2:02:40
good. So this means the shorter combination wins out and gets to stay, right. If I look at this code, it needs a little bit of work, because the first time I find some combination, I know that I be comparing that array length to no dot length, right? Because shortest combination starts as null. And I can't do null dot length in JavaScript. So I'll need like a nice or clause here. So I'll say, if it is the case that your shortest combination
2:03:06
is equal to No, then you can go ahead and replace it. Cool. So this sort of check over here is going to make sure that I automatically replace this null value with the first valid combination. Even if right now it may not be the shortest, right later on, I'll compare that combination I have stored to some possibly shorter combinations. Cool. So this code is looking pretty good. Let's go ahead and give it a little test run. Nice. Notice that and
2:03:36
on occasions where we call besam, with a remainder that is negative because remember, sometimes we subtract a number that is maybe too large, that's okay. Because that will actually bottom out at a base case and return null, which we sort of check for explicitly in this if statement. Cool. So let's give us code a run node best some. So I get an error over here looks like I get maximum call stack size exceeded, which means that we didn't really hit our
2:04:02
base case. So there's some work to be done here. So let's take a look at this code. So if I take a look at this code, it's a very, very small typo. It's kind of unfortunate that it breaks the entire code. But really, I messed up when I iterated in the for loop over here. So here I wrote for letting them in numbers, that would actually give me the indices of the array. So they'd be like 0123. Whereas I want the elements of the array,
2:04:28
right? So instead of in any of over here, so that's on me. So with that small change. Let's give it a run now. Yeah, it looks like we're passing these first three examples, we have 735, and four, four, notice that the order among the elements in the combination doesn't really matter too much. But looks like we're definitely a little too slow on this last example, over here, right? So obviously, we know the move is to memorize this because
2:04:55
we have the brute force recursion. But before we do that, let's just talk about the complexity of This. So this code is going to be very similar in complexity to our last how sum function, sort of compare the two, it's almost the same code, right? But do these side by side, right, these two functions look very, very similar. So we know in the long run, we probably have the same or close to the same complexity. Let's be methodical. So we
2:05:19
know that over here, we always like to say that M is the target sum. And we'll also go ahead and say that n is the numbers dot length. So we just did the brute force. And our brute force shouldn't be the same story as last time. So talk about the time. So the time of the brute force is going to be some sort of exponential, right? If you remember that tree drawing, in general, the exponential number of nodes in a tree will be the branching
2:05:48
factor to the height power. So not the branching factor here is n, right? I branch for every choice of number, and then the height of the tree would just be the target sum. So that's n to the M. But along with that, we also have some additional operations, right? If I look at this for loop, so this for loop gives me the branching factor, right. But then I also do this operation on line 11, which is copying over the array of remainder combination. And that array in the
2:06:16
worst case will be of length m, right? The largest sort of combination, give me back is a combination that is just filled with a bunch of ones, right? If my target sum was 50, the longest combination possible would be a bunch of ones, so 50 ones in an array. So what I'll do is, I'll say that for each of these n to the M power calls, you also have to do a linear operation in M, right? So like before, it's n to the m times m. Cool.
2:06:43
And then the space complexity is sort of interesting in this one, because we're maintaining some values. So look at this. So I talked about the space complexity, just from the stack space, it would just be the heights of like the recursion. In other words, it would be m over here, right? So I know it's going to be at least M. So I'll jot that down. But then we have also like this variable on line five, right? So I know that over time, I'm
2:07:08
going to be storing an array inside of this variable. And this array is going to be in the worst case, m in length, right? So what I'm saying is, every recursive call would have to have its own shortest combination variable, right? If the shortest combination variable is going to be an array of length m, that means I have an array of length m, for every recursive call right? Before I bought them out, at like my final base case. And
2:07:31
so also, the space complexity here is m times m, which we know is the same thing as m squared, right? And sort of the reasoning is, your maximal stack depth is still m like last time, however, now you need to have those stack frames, you need to store in array, right as you recurse. Nice. So really, the limiting factor for us right now is going to be the time complexity, which is exponential. And so like we always say, let's go ahead and
2:07:56
memorize this. So memorization pretty trivial right now, right? You've done it many times. So I'll just begun my initially empty memo object. And I'll check, you know, if my target sum is in the memo, then I should actually return the stored value. So return memo at Target sum. So now that I have my memo checking logic, what I also want to do is add the memo storing logic, right. So I need to just go to my return value and store it in the memo
2:08:23
before I return it. Notice that the return value right now, it's no longer inside of the for loop, right in the last problem, it was in the for loop, because I can return early. But this time, we're going to return at the very end, so I'll replace it over here. So I'll say, for here, the memo at Target sum should be stored with the shortest combination, I can still return the shortest combination. And before I forget, let me go ahead and pass
2:08:46
down the same memo object by reference. Alright, nothing too much to that. Let's go ahead and try this last example. Now. Give it a shot. Awesome. And there we have it. We have 425 in this last example. And that is the best way to generate a 100 is pretty evident that we cut down on the runtime. So let's talk about the memoized complexity embolized. And so the time is obviously much faster should not be exponential. But if I take a lay of
2:09:16
the land, I know that now that every target sum is going to be a key of the memo object. And target some is really just a number, right? So if my target time is 50, then I basically have 50 different keys I can never store in the memo object. So if I have m different keys in my memo object, I know that I won't be exploring any full duplicate sub trees for each of those keys. However, I will slap the branch for every number in the array,
2:09:43
right? So overall, I'm looking at an m times n. So so far, I have m times n, but I have some additional work from this array, right? So notice that the n over here that comes from this for loop, I'm iterating through numbers, but then the additional M comes from copying over this array, which would be linear. So it would be m times n times M. And I can just kind of squish these two M's together. So it kind of boils down to m squared, times
2:10:13
n, which is really the same thing as last time. And our space complexity would also be the same as it was last time, which was just m squared, mostly coming from the memo, right? And the logic is, your memo keys have m possibilities. But for each of those keys, their value can be an array of length m, right? So just m times m, or m squared. Awesome. So looking at this code, you probably, you know, feeling that Oh, my gosh, like this
2:10:40
best some problem is pretty complex. And I think it you know, to be honest, it is, however, what I really want us to focus in on is this, like progression we took, right, I think that everyone could tackle this best some problem, if they warmed up and really understood simpler problems like can some and how some write the code is very, very similar. So to wrap things up, I will let's do some closing words on the drawing board. So in its best some problem, right, we had two inputs, we
2:11:07
had m as our targets, and also say that n is the length of the array. So the brute force that we initially implemented it with just some recursion was exponential in time. And after we optimized it, we brought it down to just a polynomial time complexity. And notice that between our brute force and our memulai solution, they actually have the same space complexity. So we definitely prefer this memoized version. So hope you enjoy this
2:11:31
series of problems. That is we worked on the can some how some and best some problems, they all had the common frame of us having some target some that we need to generate with some options given in an array. And in particular, if you look at the can some problem it asks us what that task of generating target some Can you do it? So yes or no? The house and problem. So is how will you do it? So what are the exact combination of elements
2:11:53
that you'll use? And finally, the best son was the hardest version? And it asked, What is the best way to do it in terms of the least number of elements of the array? So there definitely is a logical progression to these problems. And in particular, they kind of capture a different variation of a dynamic programming problem for our can some problem, right, we had to return Boolean there. That's a type of decision problem, right? Yes or
2:12:15
no? Can you accomplish this task? Is it possible? Along with that the house some problem was a combinatoric problem, right? We want to know the exact combination that works out. And the best some problem was a variation of an optimization problem, right? I want the shortest way to generate the target. So we saw that these three problem types definitely have some common ground, but they also have some nuance, depending on exactly the question
2:12:36
we're trying to answer. These all fall under the umbrella of dynamic programming. That being said, dynamic programming problems aren't just limited to number inputs. All right, I think it's time to work on another prompt, let's say I gave you this, what I want to do is write a function called can construct that takes in some target string, as well as an array of words in a word bank. My goal is to return a Boolean indicating whether
2:12:58
or not I can make the target by concatenate together elements of the word bank. And along with that, we can reuse as many elements as the word bank as we see fit. Alright, notice that in this problem, we're looking for a Boolean response to start, right. So just yes or no. Is it possible to generate the target? So let's take a look at an example here. Let's say I gave you this. So my target is abcdef. And I have a nice long array of
2:13:22
some words. And so I'm basically asking, Can you construct abcdef, using elements of the array. So if I kind of take a look at the array, there is exactly just one way to generate the target string, which are just B, A, B, C plus D, F. So the answer here is true, because there is at least one way to make the target, right. Let's take a look at the opposite example. So let's say I had this word of skateboard. And I gave you all of these words in an array.
2:13:50
So take a moment to kind of look this one over. And you tell me write Is it possible to generate skateboard here? And the answer here is no. Right? It is not possible to generate skateboard using this array of words. So we should return false, we can get pretty close to making skateboard. But we can never build the full string. Alright, so here are a few ways that we can attempt but they don't work out in the long run, right? This is one series we can take, but we kind
2:14:15
of get stuck, as well as this. And also this way, right? Point being there are zero ways we can ever generate skateboard. So we should return false over here. Awesome. So I think let's look at one more example. We should already have the vibe that in general, it's easier to create a shorter string than a longer string, right? To create a longer string, you're probably going to need to use more elements. So if I have that kind of framing
2:14:40
in mind, that I know that possibly the easiest string to create would be the empty string, right? So let's say your target was the empty string and I gave you you know, some kind of random array of words, really, the array of words doesn't really matter here. I think no matter what they should return true. Because to generate the empty string, you can just take no zero elements. From the array, and that kind of line of thinking is going to
2:15:03
help us really start to solve this problem. So we'll kind of take this example, in stride, what we want to do is return true if our target is empty, and that takes place no matter what array of words we're given, right? Cool, more or less, that kind of sounds like a base case, right? But let's go ahead and start to kind of define some process we can take to explore all of the options, right? So I want to really visualize this in a well ordered way. And
2:15:28
that really means a tree. Right? So let's say we're going to trace through this example visually. So my target is abcdef. We already said that, in the long run, we should return or conclude a true about this input, right? So we'll just start with the input argument that is the target string as the root of this tree. And this is sort of a scenario where like, Alright, I have two inputs, how do I know which one to really encode in my drawing?
2:15:52
Well, it's about what will actually change. I know from like, one instance of like this problem to the next, the array of words, I can actually reuse as many times as I need. So it's not like I'm taking out elements from the array. So with that in mind, I think it's better or more reasonable to encode the actual target string into the nodes of this picture. Because I'm gonna start with this original target string of my route. Now I have to think
2:16:16
about how I transition to the children of this right, so what moves do I take that hopefully shrink the target string, right, I know I need to shrink the target string, because I already have the base case of the empty string in mind. So I need to get closer and closer to a length of zero. We'll talk about one transition we can make. So I know that I need to sort of use the array of words as I transition. And so let's say I took a B
2:16:41
as a choice right now, if I take a B, then I guess I could remove, you know, that sequence of characters from my parent node. So if I take a B out of abcdef, then the resulting child is just C, D, F. Cool. So notice that as we transition from one node to the next, looks like we're taking out that substring. In a similar way, I have another substring, that I can take out for my word bank, and that would be ABC, and that would yield in
2:17:08
the child d f. And then I can do this for some other string inside of the word bank. And the really important thing to know is, there's a correct logic to doing this. And it's also a common trap I see a lot of students fall into when it comes to this logic. So right now I'll talk about like the common mistake. So it would be ill advised to sort of take out the CD from our root node, if you took out C, D, then the resulting note
2:17:34
would be a, b, f. And so what we're doing right now is if we took out C, D, you're taking out something in the middle. And if you take out something in the middle, that means that your resulting string actually creates a new adjacent sequence of characters. In other words, I know that this is kind of suspicious, because look at this little run of characters, A, B, E, those are now like adjacent next to each other. Whereas in the original string
2:17:58
of abcdef, A, B, he was not present, right. So if I kind of take out strings in the middle, then I'll have this sort of mistake of creating new adjacencies. Right. And that would actually impact the moves I take later on. So I don't want to do that, right. So the move here is to not take out any characters from the middle of the string. So what would be the correct way of doing it? Well, if you look at our two nodes that we already branched into, a
2:18:26
common factor for them is the fact that we actually took a prefix out of our original root node, that is a B as a prefix, and so is ABC or recall that a prefix is just a string, that kind of begins some other larger string. So if I want to transition to a third node over here, there's only one more prefix I can take. And that would just be ABCD. Right? If I take that prefix out, then my resulting child is just E, F. And so the overall logic
2:18:54
that we want to use when we build this tree is to only branch to children if we have a matching prefix in the word bank. And of course, the child would be the resulting string after we remove that prefix. So let's keep it rolling. And we'll apply this logic again and again, recursively. So let's say I'm rooted at this CDF node, I'll look inside of the word bank and notice any prefixes that actually match here, I think there's only one and that would
2:19:19
just be CD. If I took out the prefix CD, then my result is E, F. In a similar way, I can do that for d f, I find that d f is actually contained in the word bang. So it's technically also a prefix. If I took the prefix def out of that node, then my result would be empty, which is pretty good. At this point, I look at some other nodes like this EF and they have no matching prefixes inside of the word bank. So they sort of bought them out in some
2:19:48
sort of base case. In the long run. If I can break down EF any further than I know that it's not possible to construct EF so that can technically return a false to the parent. Mr way, if I ever run into the empty string, that means the job is done. And I can just return true, right? Something we said earlier was, whenever we want to generate the empty string, it is always possible no matter what. And now this pattern should feel a little
2:20:13
familiar, right? All I have to do now is kind of bubble up these Boolean values to the parent. And overall, if one of my children return true, then I myself will return true, right? So I'll bubble this up a little bit, bubble up all the way to the top. So our root note chooses basically the true value among these three values it gets from each of its branches. And so the ultimate answer here is just true, right. And it is possible to generate abcdef
2:20:38
using words of this array. So you're probably having deja vu right now, right? We almost use the same exact logic for the previous some problem. However, all we did was adjust how we transition from one note to the next, really making a compatible for this string data. But we're going to carry over a lot of knowledge, right? It's really important that we understand like the general like knowledge of dynamic programming and recursive understanding,
2:21:01
we can apply that under any circumstances. That being said, let's look at one more example. What I want to do is see an example where this should return false. So let's say I gave you that skateboard example from before. In the long run, this is going to return false. If I tried to break down skateboard, I would always try to transition using any matching prefixes from the array. There are two prefixes at the start that match, and that would be
2:21:23
SCA and SK, and those would give me t board and eight board, respectively. And now at this point, if I route myself at the keyboard node, I can only take the T, resulting eboard. In a similar way, if I am at the eight board node, then I can only transition using the eight. And I'm left over with board. At this point, if I look at eboard, that node over there actually hits a dead end, right, there's nothing I can actually take out of Eve or
2:21:51
there's no matching prefix, because I basically need something that starts with E, but no words of the word bank start with E. So I guess we have to focus our effort elsewhere. Looking at this board, I can take either a Bo or a Bo AR, and I'm left with art and D respectively. And unfortunately, those two nodes at the leaf level also bottom out, right, I can't transition further and take out any prefixes from those strings. So I know that
2:22:18
those will have to return false. And if all of these leaf nodes return false, then my ultimate note at the top that is a skateboard node at the root, that's going to just return a false as well. So it's pretty clear to me that the overall logic we want is if we get back a single true, then we can just return true all the way up to the call stack. But if everything is false, then we'll just go ahead and return a false. With that, I think we're ready to code this one out. All right, let's
2:22:44
go ahead and code this one up. So here I have some initial examples we can use to test our code for correctness. Looking at the last example, over here, it's a fairly long one. And notice that the target incident F, whereas no words of the word bank have an F in it. So we know that that should result in a false. So let's go ahead and lay down the base case for this. Like we said, a reasonable base case is to check if your target is empty,
2:23:09
right. If you have the empty string, then you can already construct the empty string by taking no words from the word bank. So you can just return true over here. And now I need to make my recursive call in a way where my target string gets progressively smaller and smaller toward this empty string. And so I know that based on the tree I drew, I need to make a choice based on the words in the word bang. So I'm going to iterate
2:23:33
through all of the words. So I'll say for let word of word bank. So I'm iterating through every element of the word bank. And now that I have the word element, as I think about when it's okay, to make the recursive call using that word, and we spoke about this, we pointed out that we need to make sure that the word is a prefix of the target. So I can do that, I can just check if the target dot index of word equals zero. So index elf will
2:24:05
just give me the index where I can find some substring inside of a larger string. If the index i get back is zero, that means that the word starts at index zero of the target. So if you're unfamiliar with this method in JavaScript really quick, let's say I did potato dot index of pot, that will tell me the index where I can find it, which happens to be at index zero. But if I looked for tayto, I would get the index of the T, the first t rather
2:24:34
in potato. So this is a really nice way I can use to check if some substring is a prefix of another string, right, the index should be zero within it. So a way interpret this if statement is if I have a prefix, then I can sort of use it to shrink the target. So I'll create another variable here. I'll call it like the suffix so that's like the string after I remove the prefix. What I can do is slice my target string. Except to target that
2:25:01
slice. And what I want to do is start picking up characters. After the length of the words I can say word dot length over here. So it's kind of reasoned out what this logic is doing. So we'll trace through this, let's say that I don't know my word. So I'll open up the note repple. Let's say my word was the string pot. And we'll also say that my current target is potato. So I know when I do target dot index of word, that is going to get back zero.
2:25:35
So this if statement would be true. And then what I do is target dot slice of word, dot length. So we're dot length is just the length of the prefix I took, right? So it would be three over here, providing the target that slice starting at index three, that would give me everything after the prefix, right? So I basically have removed pots, and got eight. Oh, cool. So when you use slice, if you pass in a single argument, that's going
2:26:02
to be the starting position of what you start grabbing characters, and you'll go all the way through the end. Cool. And that's the logic I definitely want here. So back to the code. Now that I have the suffix, I want to make my recursive call on that suffix. So basically asking, Hey, is it possible? Can I construct the suffix now? And I'll pass along the same choice of word bank. Nice. So here's where I should think recursively.
2:26:29
So I'm focused in on what type of data do I get back from can construct I know I get back a Boolean, right? True or false, it tells me whether or not the suffix can be made. And I want to check, you know, if this call returns true, maybe I'll be explicit here. So if the recursive call is true, then I know that the original target can also be made. So what I'll do is return true early here. Cool, I know that if the suffix could be made,
2:26:58
and the word that I use to generate the suffix is also in the word bank, then the entire target must also be able to be made. Nice to hear I have my nice early return true. Like you expect, where should I return false, it should be after the for loop, right? Only after I've tried every possible choice of the word and none of them worked out, then can I say, No, the target cannot be created. So I want to do a late return false over here.
2:27:25
So this code is looking pretty sharp, I think let's go ahead and test these examples. So I should get true false true, and then false for the last one, give this a go. So I get true, false true. And it looks like the last example over here is taking quite some time to finish. So I think our code has correctness. But it's not efficient enough to you know, reasonably run this last example. So I'm going to kill this program. If you
2:27:56
take a look at the example I pass it for this last one, it does sort of describe the worst case here. For one, we know that the answer is going to be false. So you will have to do a full exploration of the tree, meaning you can't do any early return trues, right. And because of like the length of the string, and also the length of the word bank, I have a very big tree, right? Notice that there's going to be a lot of prefixes at work here,
2:28:22
right? every element of this array is actually a prefix that could be found over here. And that happens again and again. So I'll tell you what, let's go ahead to the drawing board. And we'll try to visualize what the exact complexity of this function is. Alright, so we implemented looks like the brute force for this solution. Let's talk about how we might want to optimize it, I think any conversation of optimization should
2:28:46
begin with actually understanding what the current complexity is. So let's say I gave us this kind of large example to sort of visualize with, so my target string is enter a potent pot, and I gave you a pretty diverse array of words in the word bank. So I'll just go ahead and kind of give us though the full tree in what it would look like, would be this pretty long tree, right, so I follow the same logic that we did in our earlier
2:29:08
examples. notice a few things. There are some occasions where I transition using a single character prefix, which is totally fine. And that kind of tends to feel like the worst case scenario, right? If you take single characters out of your target string over time, then you're going to have a very, very tall tree height, or you're gonna have to take many, many steps. So that kind of reminds us of a worst case scenario, like we saw when we
2:29:32
ran the code. But that being said, we want to generalize this understanding right for basically some generic size of our input. So let's say we kind of just looked at this tree in terms of its overall shape, and then we'll kind of generalize it. So to me, this tree has this sort of basic structure. And let me start by defining the terms I'll use to describe the complexity right. So I'll say that M is the target string length, and
2:29:57
n is the number of words in the word bang. Right, so I'm really trying to use a different variable for each of my inputs, because I have the vibe that both of them contribute to my complexity, possibly in different ways. So you've seen, you know, us analyze trees before in terms of like their structure, right, we're visualizing as a call tree, I know that the time complexity would be the number of nodes in the call tree, right. And so let's
2:30:21
start with some familiar territory, I kind of already know that I need to realize the height of this tree, the height of this tree is going to be m, right? Remember that m is our target string. And so imagine, in the worst case that we took, or we had to take a bunch of single character, choice of words to construct our target string, that means that the number of things I would have to take all the way from the root to a base case,
2:30:47
or the root to the leaf would be exactly M. Right? If I had to take a bunch of single characters, so we can be confident that the height of this tree would be m. So I talked about the height. Now I need to realize the branching factor, that is from one level of the tree to the next, how does a number of nodes change in the worst case? Well, I know that the branching factor is dictated by how many words I have in the word bank. And so
2:31:10
that would be some relation on n. So I know at the root level, I have about one node. But then in the worst case, to get to the next level, I will multiply by n, right? Imagine that, basically, almost every element of the word bank was a matching prefix, right? So you'd multiply by n. And let's say that carried over further, let's say almost every word of the word bank was still a prefix of those resulting nodes, I would keep multiplying
2:31:34
by n. And I would do this overall m times, right. So we already know that this is going to be exponential, I need to multiply n by itself, m times over. And so this would give me an N to the M, time complexity. In general, if you visualize your recursion using a nice call tree like this, then the overall time complexity is going to be the branching factor to the height power. So we have a branching factor of n and a height of m. That being
2:32:04
said, this will just really consider the number of calls that we make, I want to be super sure and make sure we didn't do any other kind of performance or costly operations inside of our code. So here's our code, same code as we did before, if you look at this code, some things I need to consider are probably line six, right? If I look at line six, that was where I did a target that slice that's like copying over a part of the target string.
2:32:32
And to do that operation, I would actually have to iterate through the target string. Right? So that would actually contribute to my complexity here. So in the worst case, would I be slicing? Well, if I'm slicing a target string, that would have like a maximum length of M, right. And so in every call to can construct, I'm going to have to do an additional m operation, if I have n to the M calls, then I can just multiply an additional
2:32:55
M over here, right. So I, I added some additional term into our complexity, just multiplying by M. Cool. And so overall, if you look at that time complexity, it was already exponential so that multiplication by m, doesn't really make it that much slower, it's really the N to the M, that makes it unbearably slow in the first place. So that was the time complexity. Now let's look at the space complexity. So if we just refer to the space complexity,
2:33:20
due to the call stack, it looks like it's going to be the height of this tree, right? Like we always say, the height of the tree would mean the maximum number of stack frames, we would need on the call stack before we bought them out at the base case, right? Because when we return from a call, we would actually remove something from the call stack, right? The height of this tree is definitely just M. So we'll say the space from the call stack
2:33:42
is just o of m. But again, we should also you know, look at our code and see if we created any other like growing structures. So we look at the code right now, I see that on line six, and kind of talking about that slice statement. Again, the slice returns you a new string, right. And that new string is going to tend to be of length M. So on every call to can construct, I'm creating a new string, I actually need to maintain it through
2:34:08
the recursion, right, because I actually slice before I return out on line eight. So because of that, I know that each of my M stack frames will have to store a string of length M. So that just means m times m in my space complexity, which is really just m squared. Cool, which isn't too bad of really a space complexity overall. Alright, so it looks like our final complexity for our brute force solution is exponential in time. And it looks like quadratic
2:34:37
in space. So obviously, let's work on improving the time complexity over here. And so hopefully, you're seeing where this is heading. Let's say we jump back into my entropion pot example. So this was a huge tree. Take a moment look at this tree, and where can we actually optimize some work away? To we're trying to do is notice any overlapping some problems In the context of our tree, that means I'm looking for any duplicate sub trees. And I see duplicate sub trees right
2:35:06
here, right? They follow the same structure all the way down even to their base cases. So I've looked at the sub trees, they're really trying to solve the same problem, right? That is they're both trying to figure out, can we construct the string and teapot, right? And if I saw that once, on the left hand side, the answer is going to be the same on the right hand side. So I can just store that information in a memo, right? So the trick
2:35:27
is here to of course, memorize it using our classic strategy. So let's hop to it. All right, here we are back in my code editor. Let's go ahead and just memorize this one. So I'll create my memo object. And here, I'll prefer to use the target as the key to my memo, I know from one call to the next, the word bank doesn't change, right? So I don't need to actually make it a part of the key for my memo object. So I'll just check, hey,
2:35:55
if my target is in the memo, then what I'll do is return the stored value of that target. Cool. While I'm here, let me also squish this down to a one liner. So I have the memo checking logic. Now I need to make sure I pass down that memo to all of my recursive calls. And then I need to actually store data in the memo. And the rule is wherever you have your recursive returns. Now, you should also store that return value in your memo before you
2:36:26
actually complete the return. Right. So for both of these lines, I'll make sure I store them in the memo. So it's a memo at Target equals that. But I still want to return that same value. So we'll return true and return false over here. Again, notice that I'm using my exact argument targets, right? I don't need to write any memorization logic about the suffix, right? Imagine if we made the call to can construct suffix becomes that
2:36:55
frames target. So the memos ation would still work properly. Right? So that looks pretty good. And it wasn't that much code, right? memoization is always this slightly extra layer, we add on top of our brute force solution. So let's try this now can't construct. Nice. And there we have that last example finishing fairly quickly, or we do get the correct answer of false over here. Alright, so here's what we'll do, we're going to head back to the
2:37:20
drawing board. And of course, we'll come up with the final complexity analysis for this function. Some classic memorization, right? Let's take a lay of the land over here. So we wrapped up this can construct problem, let's describe its final optimized complexity. So again, like before, we'll say M is the target length, and n is the number of words in the word bank, our original brute force had an exponential time complexity, right,
2:37:45
and that was n to the m times m. And when we memorize our solution, we actually improved it from exponential. So now, the time complexity of our solution is n times m squared, right. And the reasoning is, now we don't have to fully explore any duplicate subtree, every time we run into it, instead, we just store the results in the memo. And we can just kind of short circuit and fetch the stored result in the memo. Notice that I have an M squared,
2:38:08
right in the memo, I have complexity, that second m really comes from the fact that we still have to do the slice, we have to pay for that cost. So although we added an additional object in our memo II solution, our space complexity would remain in the polynomial class. So overall, we definitely prefer this second solution, because we remove some exponential, you know, complexity. So now it is reasonable to actually run this in an amount of time.
2:38:32
I think that wraps up this can construct problem. Now let's work on the counting version of this problem. In particular, I want to work on count construct. So we have the same set up here, I want to take in still a target string and also an array of words in a word bank. But this time I want to return a number, I want to return the total number of ways that the target can be made using words of the word bank. And like before, we can reuse
2:38:54
elements of the word bank as many times as we want. So notice that this question asked us to do something slightly different, we don't want just true or false. If it's possible, we want the exact number of ways that we could construct the target string. So let's take a look at some examples. And also, you know, take a high level view of the strategy here. So let's say I gave you this string of abcdef. And this array of words, this particular example
2:39:18
we saw before, and it is possible, and there's actually one exact way we can generate abcdef. So we can construct the tree in the same way we did before. And we end up with this. However, this time around, we want to choose a different value to return for our base cases, as well as changing the logic for reconstructing our sub solutions, right? And so if I look at the base cases here, I wanted to kind of just adapt the return value for this new type of data that I need
2:39:43
to return which is number. So I think the move is for these scenarios where we can't break down our current target any further. That's your return zero, right? Yeah, f can't be broken down because it doesn't have any more matching prefixes from the array. So that means there are zero ways to breakdown F. And so we should return zero in those scenarios. And then when we have the empty string we know was successful. So we could always, you
2:40:08
know, create the empty string. And so that should return one. And we've seen this logic before in problems like Fibonacci, as well as our grid traveller problem, we just want to bubble up these values to their parents, and make sure every parent will add up all the numbers that come back from their children. So it just bubbles up like this. And top level we do zero plus one plus zero, which means that we can generate abcdef in exactly one
2:40:31
way. And if you look at the way that actually is symbolized inside the tree, it's exactly the path from this root node all the way down to that lone base case that returned an empty string, right, ABC plus d f. Let's take a look at another example. So here I have the target string purple, and I have some other characters and words inside of the array. So take a moment to look at the input here and predict what number they should return.
2:41:01
So the answer here is two, right, there are two ways to create purple. So if you construct the tree, we know we start with the initial unknown of purple. And then we have about three prefixes that match here. And those yield some children, we can follow the same pattern recursively down the tree. So the full tree really looks like this, notice that I have a two base cases that actually end up as the empty string. So I know those are
2:41:28
going to turn one up to their parent. And on the right hand side, I have a loan II that can't be broken down any further that returns zero. And like always, right, I just bubble up these values, until at the parent, I actually do one plus one plus zero, which gives me two. All right, there are two distinct ways to create purple using this choice of word bank. All right, I think I'm feeling pretty good about jumping into the code for this
2:41:49
one, it's really just a small variation of the last problem we did. So let's hop right in. Alright, programmers back in the code editor, let's go ahead and bang this one out. So I already have some examples that show us what numbers we should return for this count construct, right. So I have some examples here. I'm gonna say even have that big example, with our large inputs, we know that that will probably need to be optimized, let's lay the
2:42:11
foundation with a brute force. So we'll start with the same base case, as always, right. So if the target is the empty string, then we have truly solved the problem. Meaning that there is definitely one way to generate the empty string, right, just take no elements from the word bank. Along with that, I need to make my recursive call. So the usual structure, right, I want to iterate through every choice of word. So for let word of word bank. And
2:42:34
then for every word of that word bank, I need to check if it's a prefix. So we've done this before, if the target dot index of word bank, or rather index of word, if that is equal to zero, then it must be a prefix. And if it's a prefix, and I can go ahead and take like the rest of the word that is the suffix and call recursively on it. So I'll do this in line now say, count construct, and I'm going to pass in the rest of the word, which
2:43:05
would be target dot slice, and then I'll slice starting at word dot length. So this means that the slice contains everything after the word or everything after the prefix. And so Also be sure to pass into the second argument, the same word bank. Nice. And now I need to think about what calc construct returns. So it's returning a number now, right? So in particular, this will be the will say, num ways. I'll say no more ways for the rest,
2:43:38
maybe a little wordy of a variable name, but I think it does describe how exactly what this returns here, right. So this is a number of ways that you can generate the suffix with like the rest of the target. What I want to do is keep a running total. So outside this for loop, I need a way to add everything that the for loop iterates through right, so I'll create a total count over here. So I'll say let, I'll say total count. And I'll start
2:44:03
it as zero. And now inside of my for loop, whenever I get the number of ways to create the rest of the string, I'll go ahead and just add that into my total count. So it's as simple as total count plus equals the number of ways to generate the rest of the string right after I've removed the word. And after I take the total through the entire for loop, and I can just return the total count. Something really great about this, this programming
2:44:31
pattern is let's say that none of the choice of words were a valid prefix. So that means I finished this for loop. And this if statement is never true. If this if statement is never true, that I never add anything into the total count. So if I return total count afterwards, I return a still zero, which makes sense because apparently there are zero ways to make the target right have no initial step to take in the word bank. So let's go ahead and test
2:44:58
this one out. So looks like we should get to 104, and then also a zero at the end. Let's give that a go. So 2104. And it looks like the last example is just a little slow for us. So you already know where this one is heading. Let me tell the program, let's just go ahead and just memorize this one off the bat, right? Hopefully, I think through all of these examples, you're feeling really good about memorization. And it's apparent that we basically have drilled
2:45:29
into our minds already. So if the target is in the memo, and just return the stored value memo at Target. And then I'll need to adjust my return value, right. So where I return over here is I'll store that total account as the value corresponds to the target. And let's not forget to also pass in the memo to our recursive calls, right? So memo goes right here. Nice. So let's give that a run again. I expect a zero for that last answer,
2:46:00
right. So looks like I have an error over here. And of course, I forgot to actually replace my return value. So I can still return the total counts. And addition to that, I'm actually adding it into my memo. So let's try that now. Yeah, these answers look correct, right, I got zero for the last one, notice that the last one is not possible, because it ends in an F and all my words only contain E's. Nice. And if you look at this code, it's
2:46:25
a pretty similar to our previous problem of can construct if I kind of split these can construct basically has the same shape. Really, the only difference is this number variable that I add into, and of course, the return values. So we do expect the complexities to be the same for these two functions. Let's wrap this one up on the drawing board. Let's look at the complexity of this. As always, for this calc construct problem, our M is
2:46:52
going to be the length of a target string, and our n is going to be the length of the array, right? So that means a number of elements in that array. Our brute force is the same as it was in the can construct problem, right, so it's still exponential. And using memoization. We just brought that down from an exponential to a polynomial time complexity, and the space complexity remain the same. Really, there is no additional cost that we pay in our implementation
2:47:15
for this counting version of the problem, right. The only difference is now we're maintaining a number that we just add to, you know, on every iteration of that for loop. But that doesn't really affect the runtime or the space complexity at all. So I think this wraps up this count construct problem. Now I want to do one more variation of the string problem. So what I want to do is write a function called all construct that has the same setup, right, so I'm going to take in
2:47:38
a target string, as well as an array of words in a word bank. But this time, what I want to do is return all of the ways that the target can constructed by concatenating elements inside of that word bank. And that means I should return a two dimensional array, a single element of that 2d array is going to represent one of the combinations that can construct the target, right, and I want to return all of the ways within a 2d array. And as always,
2:48:01
we can reuse elements of the word bank as many times as we need. So let's make sure we understand this question by looking at some examples and their output. So here's an example using purple. And it's the one we've seen before in the last problem. The last problem I had us return to because there were two ways to create purple. But now I don't want the number, I want the exact ways that actually create purple, that means you
2:48:22
need to return a two dimensional array, the outer array, or the outer set of brackets represents the collection of all combinations. Whereas a set of inner brackets or a sub array represents one of the combinations that creates purple. Let's take a look at another example. Let's say I gave you abcdef. And I gave you this long array of word bank, notice that I actually added some elements inside of this word bank array. It's a little more complex
2:48:45
of in our previous examples. Because of this, there are actually many ways you can create abcdef. And this contains all of them, right? So there are four ways to create our target string. And again, notice that each sub array represents one of those combinations of words in the word bank that creates the target. Cool. So now that we kind of understand like the shape of this problem in terms of the data we should return, let's take a look at
2:49:08
some base scenarios. So let's say I gave you this example. Right? So I have a target of Hello. And my words in the word bank are just Cat Dog and mouse. Obviously, you know, that is not possible to generate Hello. So there are really zero ways to create this. How should we actually return an answer here? Well, I think it'd be reasonable to return an empty array. Remember that we're saying the outer array in this context represents the collection
2:49:34
of all of the combinations that can create Hello, since there are zero ways to create Hello, that means that our collection is empty, right? This has a length of zero meaning there are zero ways to create Hello. Now let's say we had another base scenario. Let's say we have to generate the empty string using the same array of word bank. And that scenario, I think it's reasonable to return an array containing an empty array. And again, the
2:49:58
reason is if it is possible to To create the target string, then we need to return a 2d array, right where the outer array represents the collection. And if there's one sub array inside of that outer array, that means there's one way to create the empty string. And what does that one way? Well, it's to take no elements from the word bang. So I think this is going to be consistent logic, this is going to be a really important way to think about this
2:50:19
problem. That is, when we're given a target that cannot be constructed using the word bank, we should return an empty array, right, a one dimensional empty array, because there are zero ways to create it. On the flip side, if I've ever given the empty string, we know that it's always possible. And so we should return like a two dimensional empty array. Cool. So with that, let's look at some tree examples. Now, let's say I have this large
2:50:40
example from before, we know that the overall tree like we've always know created would look something like this. Obviously, now we're just reframing this problem in the return values that we do for our base cases. So you notice that there are four base cases here that kind of reach the empty string. And I know that those represent the four ways to create abcdef. And now I have to adjust the return values here. So I'm already saying
2:51:05
that if I have the empty string, then that should return an empty 2d array. So it looks something like this, right? And how I actually reconstruct the entire solution from these very small sub solutions. So let's just stay focused on the left subtree. Right now, I know that these arrays are going to return back to their parents. And when I do that, I also need to make sure that I include the edge that I actually use to transition to
2:51:31
the child. In other words, I'm going to be sure to push the label for the edge into each of those sub arrays. So the key insight is this, right? I'm just pushing those edges into their sub arrays. And from here, I continue the pattern up a little further, right. So I know that these arrays return their parent over here, and I still, you know, push the edges that I took to get to those children. So on the left, I'm going to put CD in the
2:51:55
front, and on the right, I'm going to put C in the front, resulting in this. And then at this point, notice that this node rooted at C D E F, that is actually going to receive both of these collections, right? And what should this note do? Well, it really needs to just combine a both of these arrays. Recall that, you know, we technically receive a two dimensional arrays, which means that a sub array represents one of the ways to create
2:52:23
the actual target. So if I just concatenate these two, two dimensional arrays, that yields this construct, if I do a quick spot check, I'll see if this is compatible with what the question is asking, right? This is a two dimensional array. And I know there are actually two ways that we can create CDF, if I look at what this is saying, The first way is to do C, D plus F. And the other ways to do c plus d f. And so this cell problem is correct in
2:52:49
itself. So I'm going to use the same exact logic to trace through the right hand side, I know that these cases return to their parent. And the parent is responsible for adding the edge to each of those sub arrays like this. Now, I'm just gonna reorganize everything at the top just to give us some more room. And maybe I'll even spread out these brackets to make a look more symmetric. But I'm not done here, I still need to consume each of
2:53:12
the edges at the very top of the tree. So if I look at my left hand set of arrays, I know that those need to receive AB. In other words, they need to have a B place at the front of each of those. So I'll just do that, right. In the same way, all of the arrays in the middle, which is really just a one sub array, need to add ABC to the front of them, like this. And finally, same thing on the right hand side with ABCD. Cool. Now if
2:53:38
I look at what I have, these represent the four ways that we can actually create our original target string. But at this point, the root node just needs to concatenate each of these two dimensional arrays together. So it really just combines them into a single 2d array like this. And if I do a quick sanity check, I know that each of these sub arrays represents one of the paths that I can take to a base case down my tree, which is exactly
2:54:05
what we intended at the start. So this type of recursion is definitely more complex than the previous examples. But hopefully, you can recognize what's similar to our last examples, right? Let's do one more together, though, let's go back to this purple example of the full tree would look like this. And we'll trace through this. So on the left hand side, we're going to start with a 2d empty array, right, because that's the base case for the
2:54:27
empty string. Meaning that hey, it is possible to create the empty string in one way, and that is to just take nothing. So I do the same logic as our last example, meaning I returned to my parent, but I'm being sure to also include the value of the edge, right. And so the key insight here is, I'm being sure to add the edge label and not the actual node label here. The note and the edge happened to have the same thing le, but I'm really
2:54:52
looking forward to adding the edge right? So I add Ellie over here. And likewise, this returns to its parent even further, and so Add that last edge of perp. Cool. Now I need to do everything for this middle path. And so what I'll do is return the empty 2d array at the very bottom. And this really bubbles up all the way to the top. And we just accumulate every edge label as we go, right. So it sort of looks like this.
2:55:20
And what's really interesting about this a right hand path, this is actually a base case, that doesn't work out, meaning we kind of hit a dead end at EA. And what we said in our initial examples was, whenever we have a target string, that cannot be created at all using words of the word bank, then we're going to return a one dimensional empty array. And that actually works out in our favor, because if we return this empty array to our
2:55:46
parents, our parent is going to try to add the edge into every element of this empty array. But if there are no elements in this array, and it's going to add nothing. In other words, this one dimensional empty array really just bubbles up to the very top. And like always, if I just concatenate all three of these arrays together, I actually end up with my final answer, notice that when I concatenate an empty array to the rest of these, I will
2:56:13
actually contribute nothing to my file answer, which makes sense because there are no paths that work out on that right hand side. So our final answer is just this. Like, we know both of those sub arrays represent the two different ways that we can create purple. All right, I'm feeling pretty good about this process. Now, let's go ahead and code it up. Alright, programmers back in the code editor, another problem, another solution. So let's
2:56:35
start by laying out the base case over here. Now, like we said, we'll say if the target is the empty string, then we want to return a two dimensional empty array, right? Every single sub array here represents the one way you can create the empty string by taking nothing right I take no words of the word bank. Nice. And then besides that, we need to make our recursive logic. So that's going to be very similar to what we've always done
2:56:59
for this style of problem. So I'm going to iterate through every word of the word bank. So I'll say let word of word bank word bank. And I need to still check if there's a prefix, right? If this word is a prefix, so if target dot index of word, if that index is zero, then I know that it must be a prefix, so I can continue some code inside. Nice. And so what I'll do is I'll go ahead and create an extra variable just to store the target after
2:57:29
I remove the word which would give me like the suffix so I'll say const suffix equals, and I'll say target dot slice of word dot length. So you've seen this pattern before. But just to refresh, this just gives us everything after the word. So basically, once you move the word, what is the remainder of the string all the way to the end. And now that I have this suffix actually wants to call my function recursively on that remainder, right? Just
2:57:56
like this, I'll pass along the same word bank. Cool. And now here's where things get a little intense, right? So we've been doing a lot of problems, you know, using this recursive structure, and then we memorize it in the long run, I think the most important thing to do is when you make your recursive call, you really just assume that your function works, right. So I think about what type I should get back from all construct. So I know
2:58:20
that all constructs and give me back an array, right, it's gonna give me back an array containing all of the ways to make the suffix. If there are no ways to make the suffix, then it's going to give me like an empty array, right. And so I'm going to assume that here, so I'll create a variable. And I'll call it, let's say, the suffix waise. And the reason I'm naming it like this is, I really want us to, in our head, think about the return value
2:58:43
from this as an array of all the ways to build the suffix. Cool. So that's going to be a two dimensional array, right? There are many ways to do it. Nice. So if this gives me all the ways to make the suffix, how can I get all the ways to make the original target like in this current stack frame? Well, what I need to do is really just take each of those suffix ways, and add my word to the front of it, right? I used this word to even create
2:59:14
the suffix in the first place. So what I can do is, I'm going to say my target ways. Right? So now I want to relate how the suffix ways can be used to build my original target, right? All I need to do is really iterate over every sub array over here and add my word to the front of it. Right, that's exactly the process we took in the tree diagram, right? So I can use some nice JavaScript methods here. If I just wanted to basically manipulate every
2:59:44
element of the array, I can do a map here. So I'll say suffix, ways dot map. And I know that a single element there's going to be one way he'll say, singular. And then what I want to do is just take that same way, copy it over, meaning I just spread It's elements. But I'm also going to put the word that I took in the front, we've seen this syntax before, although maybe this like map method is maybe new free, maybe you're not super
3:00:12
familiar with JavaScript. I think that's fair game. So let's hop into the node repple. Just to demo this, let's say I had some array, I'll just make this array 1234. So there's my array. What I can do in general is use array dot map. And map is a function and you should pass in a callback. So that means another function. And what I'll do is this callbacks gonna take in every element, and it's gonna be an arrow function, what's going to return
3:00:38
is really just how I want to modify the elements, let's say I wanted to multiply every element by two, right, the return value of this callback function is going to become a new element of the new array. So notice, I get back 2468, my original array was 1234. And I get back a new array using map. And so essentially, what I'm doing in this example, on line eight, in my actual code, I'm just taking every sub array and just inserting my word at the front
3:01:07
of every sub array. So an example that speaks closer to our exact code would might look something like this, like suffix ways. And it's going to be a 2d array. So I'll make a sub array, and we just an array of some strings kind of arbitrary right now. So I'll say x, y, and then z. And then the second sub array will be maybe I don't know, like, a x and then a yz. Right, so that's my original array. And what I want to do is, if I say
3:01:34
suffix ways dot map, and let's say for every way, that is every sub array, I just want to copy over that way by spreading out. And then I'll just go ahead and put I don't know, like an A at the front, just like this. So notice what I get back, I basically have every sub array from before, except now I have a as the first elements of both of those. Cool. So that's all I'm doing in this particular chunk of code. Awesome. So we'll leave the
3:02:02
node repple. Back to our running solution. And now that I have the target ways, that's good. It's basically just like a piece of the answer I need. However, it now this is really only going to give me all of the ways to make a target that use this word that I'm currently like on in my iteration. However, I know that this for loop gives me multiple branches, right, it's going to use all of the words that are possible to create the
3:02:28
target. So I need to kind of gather them all together. So I'll create a variable on the outside, I'll call it result mailstore. Everything right? So across all of these iterations, I just want to add the target ways into the results, I'm going to do result dot push target ways, and I need to actually spread this out that way, I don't nest things too deeply. Right? Remember that this is a one dimensional array, right now, target ways would be two
3:02:56
dimensional, I don't want to just push target ways into result. Otherwise, I'd get like a three dimensional array. So I'm going to be sure to spread out target ways, right. So with that, let's actually go ahead and give this run I think all I need to do now is after my for loop, right, after I'm done getting all the ways, then I can just return the results of Mr. Just work recursively. So let's just try maybe the first example for now and see how we do. So I should get,
3:03:25
you know, a two dimensional array where I have two ways to make purple. Right? let's give that a go all construct. Nice, and that's looking pretty good. That is a correct answer. Let's try these other ones. Now while we're here. So we should get a nice, large array for that second example. Nice, here it is. And then the third example, skateboard should return just an empty array, because it's not possible. And it looks like that last example
3:03:49
is also not possible. So we do get an empty array. And if you kind of notice, to get that last answer, like we did in our other examples, it does noticeably take us some amounts of time. But before we get to that, let's take a look at this code, make sure we really understand it. So the biggest logical leap we made here was really, you know, assuming that we get back valid data from line nine, right? And then it's all about how we can, you know,
3:04:14
adjust that sub result to get our full answer, right. So if I get all the ways to make the suffix, and for each of those ways, I can just add my word in front of them. And that would give me all the ways to make my target. Right. And I need to continue that process for every choice of word, which is why I'm maintaining this like a massive results variable outside of the for just pushing all the ways into this result over time. And maybe just
3:04:40
to be super clear, you're not familiar with like this push method, especially when you use the spread operator with it as well and really easily step through that. So in isolation, right, this is just using push and spread in general, if I had some, let's say, array, and let's say it was just an array of just some elements 1234 Then I had another array, I'll call it just numbs, let's say in nums, I had elements of seven and eight. So here's
3:05:10
my original array. And here's my nums. And if I did array dot push nums, you're actually going to force some nesting in this array. So array dot push returns the new length. But it also actually manipulates or mutates, the argument you call it on. So if I look at the array, now, notice that it actually has another array nested inside. That's because I literally just pushed the entire nums. If you wanted to do something a little different,
3:05:38
what you can say is array dot push, and you spread out nums, what's going to do is comma separates the seven and eight, basically removing the outer brackets from it. So have a look at this. Now, look at the array. Notice that with that second push, now I just added a seven and eight without those additional brackets. So that's all I'm doing over here. Like I said, I don't want to add another level of nesting to the result array, right, it should
3:06:02
just always remain at most a two dimensional array. Cool. But overall looks like we have solved this one. And let's kind of talk about if there is even a way to make this faster. This is kind of an interesting problem. So this is looking pretty good. So earlier, when we were on the drawing board, we said that, alright, because of what they're asking in this problem, it is basically going to require a full exploration, right? If I want you to
3:06:31
return every possible way, to make the target string, you'll just have to kind of do all the work of creating all of those sub arrays, right, so we can't really avoid that stuff over here. If you think about this example, unlike 3334, this is actually not the worst worst case anymore. All right, here, we know that eventually we're going to return just an empty array, because we can never generate the final z in this example. However, if I
3:07:00
remove the Z, then the result will be a very, very massive 2d array, because there are a bunch of ways to actually make this target string. Right. So we've kind of changed the direction of what it means to be like worst. On this example, let's say we brought this to use the Z. If you really cared about optimizing, like this particular scenario, you would find some benefit to like memorizing it, although it wouldn't really affect the worst case,
3:07:27
because the worst case is actually where you return a two dimensional array and not just an empty array. So maybe just because it's good practice, well memorize this. But when we go to the drawing board, we'll see that this actually doesn't affect the true a bigger worst case. But if you just want to optimize it slightly, let's say we baked in our memo over here, then we check, you know, if our target is in the memo, and if it is, then
3:07:52
we return the memo, add the target, we'll be sure to pass along that memo to our recursive calls. And then we just need to make sure that for our return value on line 16, we actually store that inside of our demo using the target as a key, and then we still complete the return by returning result like we once did. Cool. So let's run this now. And I would agree that the last example now runs faster. But it is not the worst case is a really important thing to understand
3:08:23
here. Right? The worst case is when you actually have to create a massive sub array, right. And so let's head to the drawing board and see our final conclusion about the complexity here. Like we usually do, well define m to be the length of the target string, and n will be the number of words in the word bank. We know that this problem asks us to return an array containing every combination that generates the target string. And to come up
3:08:49
with that answer, we have to visualize it like a tree sort of like this. In our previous drawing, we saw how each leaf of this tree represents one way we could create the target string. In other words, if we can figure out the total number of leaves in a tree like this, then we will basically have the number that represents how many different ways or how many sub arrays we have to generate in this problem. We already know that based on
3:09:13
our process, we described that there are dimensions to this tree, we know that the height of this tree is going to be m and we know that from one level to the next, we really just multiply the number of nodes by n. And that means at the base of this tree, we would have entity m number of nodes, right, so we have n to the M leaves, which means that we have n to the M different combinations that generate the target string. And if we have to represent
3:09:38
each of these entity m combinations, then we definitely need n to the M sub arrays in our output. And so what we're saying here is no matter what clever implementation we create, we really have to return a result that is exponential in size. And that's really going to drive the complexity of this one. You can't do any better than exponential over here. And its overall will say at the time. complexity of this is n to the M or just exponential.
3:10:02
If you want to split hairs here, you can really multiplied by some additional factors of m. However, the exponential nature of this alone really gives us the overall complexity, right, because once something is exponential, there's really no coming back from that. And in a different vein, we can say that this space complexity for this is O of M, like we usually say, it's really just the height of the recursion tree. And an example like this, where output
3:10:25
is very large, we usually don't include the size of the output of the size of the result into our space complexity, which case obviously, would also be exponential in space, because the result is exponential. Right. So here, we'll just refer to the additional space we use for the call stack, which would be o of M, right, any solution you come up with for this problem would be just about this fast. Alright, and there, we have our all construct problem.
3:10:54
So at this point, we've gone over many dynamic programming problems, and we use that memoization strategy to work out a solution for all of them. However, memoization is only one of the ways we can actually implement a dynamic programming solution. Right now I want to revisit all of those problems, but this time use a different lens of understanding. As always, I want us to ease into things. So we'll warm up with this fib function, this
3:11:15
is the same problem as last time. In other words, I want us to return the F number of the Fibonacci sequence. Here, I'll say that the zeroeth number of the sequence is zero. And the first number of the sequence is one, you might notice that this time around, I'm saying that the zeroeth number is zero and the first number is one. Whereas in the first time we did this, we said the first number is one and the second number is one However,
3:11:34
no matter how you start the sequence, they will both actually give you the same series of numbers. In other words, down below here, I have some examples for n as well as what the output for our fib function should be. In other words, if I asked you for the six Fibonacci number, the answer there is eight, like we always expect, alright, let's get into the heart of this strategy, right? What does tabulation even mean? Well, it's all
3:11:54
about building a table. So what we'll do now is step through a tabulated strategy for calculating fib of six. I know that in the long run, I ought to return the final answer of eight, right? So I hope that I get the answer right by the end of this little trace. So with tabulation we're choosing to do is really think about this dynamic programming problem, still in terms of subproblems. But instead of doing it recursively, we do it iteratively by building
3:12:18
a table, really just an array, and I'm going to begin it with roughly the size of the input. In other words, if my input here is the number six, then I basically want an array of length six, notice that if I want the indices of this array, it's kind of line up perfectly with the original input number. And I'm going to have to actually add an extra position. In other words, this array spans indices zero through six, which kind of means that there
3:12:41
actually are seven different elements here, right, the length of this array is seven. So something very common that I see when students try to implement a tabulated strategy is they kind of overlook this off by one nature, right? So technically, I'm creating an array that has one greater length than my number input. But any case, if this is my array, what do I want it to represent? Well, in the long run, I want to actually fill out this array
3:13:06
in a way where each subproblem corresponds to an elements of this array. So here's how I'm going to begin this table. The move here is to actually initialize every position of this table with zero. And the reason for me initializing zero everywhere in this array is the fact that I know Fibonacci requires me to take a sum, right, and zero is a really great starting value when I need to calculate a running sum, right. But along with that,
3:13:29
I need to be sure to seed the starting values within this table. In other words, if I look at the zero position of this table, it already has a zero, which makes sense because the zero number on the Fibonacci sequence is zero. But what I should also do is make index one contain a value of one. And that kind of entails that, hey, the first Fibonacci number is indeed one. And now at this point, once I've seeded those initial values, now I can actually run
3:13:55
the general algorithm to fill out this table. So now it's just a matter of iterating through this table, so I'm going to start you know, at the very first position of the table, probably just with a regular for loop. And what I need to do is really remember the definition of Fibonacci, right. So if I have this number, currently in the array zero, that's a zero Fibonacci number, what I can do is just add this current number that I have kind of pointed
3:14:19
to in yellow to the next two positions. And the reasoning there is a Fibonacci number is used to contribute to the sum of for the next two Fibonacci numbers. So I'm going to do is take the zero and add it to the next two positions, obviously, since it's zero, actually don't change the values of those next two positions. It's nothing really is calculated on that first iteration. But any case I can continue on to the next iteration,
3:14:42
so my current position is always in yellow, and the next few positions are pointed to in blue. At this point, my current position says one is what I should do is take one and add it to both of my next positions. So that means two and three are indices two and three are contained both a one and a one which so far, make some sense because at least for the to the second number of the Fibonacci sequence is indeed one, I can do the same
3:15:07
thing, right, my current position contains a one. So I'll add that one into my next two positions. Keep doing this, I add two to my next two positions, at three to my next two positions. And at this point, I sort of reached the end of my array. So I know that I probably shouldn't step out of bounds. So really just want to look one position ahead over here. And at this point, I just add five into my next position, which actually works out to an eight being
3:15:34
stored in index six of this array. Which makes sense because logically, the six number of the Fibonacci sequence is a just like we intended. That's all there is to tabulating Fibonacci, the most apparent difference from our previous like recursive strategy was, this is not recursive, right? This really just requires us to iterate through an array. So to fully iterative process. And at this point, the actual complexity of this is really straightforward to kind of
3:16:00
foresee, we know that we're just going to iterate through an array of size n, that must mean that our time complexity is just n. In the same way, the only space we use is really just the space of the array, which I know is still going to be sighs and as well. So overall, we're looking at a linear solution for fib. So before we hop into the code, for this one, I just want to draw a really important connection. So although at face value, this
3:16:23
iterative strategy looks very different from the recursive solution, a lot of the logic really carries over, I'm still using my overlapping subproblems to solve this one. So for example, I know that every index of this array really corresponds to some number input for fib of n, right? So I can kind of visualize it like this, right? Like we said, the six of bonacci number is eight. So I'm just going to choose a position of this table, let's say I looked
3:16:50
at fib of six. So I know that to calculate fib of six, what I did was really add the previous two numbers into this position, right. And if you kind of see that the shape of this, I kind of dropped the table, and even just ignore the rest of the subproblems. This is basically just a tree that can kind of shift things around. And it really looks like this. So overall, you're looking at really the same relationship for calculating Fibonacci. It's
3:17:17
just encoded in a table instead of the recursive tree. But overall, if you understand, you know, the recursive solution, you should still find, you know, some comfort inside of this iterative solution. But I think at this point, let's hop into the code for this one. Alright, programmers, let's go ahead and translate that strategy into some code. So I'll start by creating a table, which really just means creating an array, we'll call this table.
3:17:42
And I need this array to have certain dimensions that are roughly the size of n. So to do that, in JavaScript, I can say array and call a static method and pass in my desired size. So here, I want to say n plus one. For the reason we did in the sketch, right, I need to make sure that the last index of this array is exactly n, I have to do a plus one here, because of course, indices start at zero. Cool, that should give me an array of that
3:18:11
n plus one size. And then at this point, what I want to do is assign particular values into this table. So let's just say I console dot log, what this table looks like, I'll just run this first example of fib of six. So I'll give this a go. So notice that the array that prints out is this, it says like seven empty items, which means that the elements are undefined right now, according to our strategy, but we should do is assign these all to zero.
3:18:40
So what I can do is, after I initialize the array over here, I can fill it up with all zeros using the dot fill method, right? It's an array instance method. So with that change, now I should have a seven zeros inside of this array. Cool, so it's looking pretty good. At this point, I also need to fill up a particular value inside of the table, I really need to make sure that the index one contains a value of one, right so I can say table at index
3:19:08
one equals one. So we're seeding index one with a value of one to symbolize that the first bonacci number is one, remember that we kind of have like two base scenarios. In Fibonacci, let's just console that log with this table looks like now to make sure it's in the correct state before we actually iterate through it. Cool. So this is a good starting point for our table. So at this point, what I want to do is iterate through the table.
3:19:32
So use a regular for loop for that. We're gonna need access to the indices. So I'll say let i equals zero. And I'll go up to and including, and basically give me iterations through the entire table. And I'll do i plus plus, I'm going to hit every position. Cool. According to what we did in our strategy. What I should do is look at the next two positions after I right, so I'll say as I'm gonna look ahead and table and I'll look at positions
3:20:00
I plus one, and also i plus two, right? Of course, right now I'm currently situated at position I. And what I did was I added into those two neighboring positions, I added my current value in the table. So what I'll say is, in my next position i plus one, I'm going to increment it by exactly what table I says, right? So I'm incrementing, my next position by the value in my current position. And the same will hold true for the next position
3:20:32
two spaces away, right, so they both get plus equals table. I know nice. So this is looking pretty good. After we're done doing this process for the entire table, where we're just going left to right, filling in our next two neighboring positions, what we'll do is just return our answer, which should be table at position n, right? To finish this off, I just want to return the table at index n, because the
3:20:57
elements of this array correspond to the Fibonacci number, right? And the index is sort of the input to my function. So let's try these examples. We'll give them all ago. Cool. So I get 813 21. In this very large number, this actually looks correct. Nice. This is a fair implementation of Fibonacci. Notice that because we're already using an iterative strategy, we already satisfy a decent complexity for even this, this last example
3:21:27
over here, we already mentioned the time and space complexity of this strategy, right, it gives us a linear time and space. However, you may already have in your head that we could actually optimize a little more here and just use a constant amount of space. However, if you want to kind of subscribe to just a generic tabulation strategy that I know is going to be useful in most problems, I will kind of stick to this overarching pattern
3:21:50
right of initializing our table upfront, that is roughly the size of the input, and then iterating through that table. Of course, you can probably finesse this fib function to only track two variables represent your last Fibonacci number, as well as your last last Fibonacci number. But I'll leave that to you because it's not really a classic tabulation, which is a topic want to drill into our heads right now. Let's head back to the drawing
3:22:15
board and do another problem. All right, now let's revisit that grid traveller problem using tabulation. So like before, we're going to have a 2d grid, and we start in the top left corner. And our goal is to go to the bottom right corner, we only have two possible moves at any point in time that is to move down or to the right. And how many ways can we actually travel to the goal, if we had a grid of dimensions, m by n. And we want
3:22:39
to write our function to actually calculate this. So let's trace through how you can build a table for this one, let's say we're going through grid traveller of a three by three grid, that means that our output should be six in the long run. So like before, our first step in this tabulation recipe, is to create a table that is roughly the size of the input. And so here I have two inputs, and they really represent the number of rows and number of
3:23:02
columns. So I can create a 2d array to correspond to that. Like before, if I want the indices to match up here, I'm going to have to make sure that this two dimensional array has dimensions four by four, right? If I give it a four by four array, that means that the bottom right index is really three comma three, which works out nicely, very similar to what we did in that last fib problem. Cool. So I established the dimensions for my table. Now I have to
3:23:29
figure out what should I actually begin my table with, right? What are the good seed values to use here? Well, I know this is a counting problem, right? Because they're asking me to count the number of ways to travel through this grid. For these counting problems. Good initial value to choose is usually zero. So I'm going to put zero everywhere in this grid. But at that point, I may need to seed another value in other position in this table, if
3:23:53
you recall our previous discussion about this grid traveler problem, we said that it's a really important case that all right grid traveler have a one by one should return one right there is one way to travel the gray one by one grid. And so I'll go ahead and actually take that information and encode it into my table. So I'll make index one one, actually contain the elements of one. And I should give me a nice starting point for
3:24:17
this algorithm. So at this point, what we want to do is iterate through this table and come up with some logic that combines the values in this table, right, basically combining different subproblems to solve my larger problem at hand. So let's just begin in the top left corner of this grid. In the long run, we can really implement this kind of iterative pattern through a grid using just some nested for loops, right. And the key insight is I know
3:24:42
if I'm at this position, if I see zero at indices, zero comma zero, that means in a zero by zero grid, there's zero ways to move through it, which makes sense, right? Because if any of your dimensions contains zero, then that must mean that your grid is empty, right? So the game isn't even valid. But if we want to have some consistent logic, the move is to use your current position highlighted in yellow right now and add it to your neighbors,
3:25:08
right, according to the game, I can only move to the right or downward. So technically, what I'm doing right now is I'm taking my current positions element, and adding it to my down neighbor and my right neighbor. Obviously, if I just have a zero in my current position, then really no arithmetic takes place. But let's go ahead and do these iterations just to make sure we have consistent logic, right, so they keep adding these zeros to their right
3:25:31
and down neighbors, nothing changes for now, until I get to the next row, right, this first iteration, next row, still just add zero to its down and write. But once I'm at this point, I'm going to take this one, I'm going to add it to my right and down neighbor. So that means they both turn into a one, I keep following this pattern, right, both of my neighbors turn into a one. And obviously, whenever I kind of reached like the bounds of my grid,
3:25:56
I need to probably make sure that I don't do any illegal Array Operations. But that's really an implementation detail for the code. So on to our next row, we contribute zero to both of our neighbors. Here, we contribute one to both of our neighbors. Now we contribute to to both of our neighbors. And here we contribute three to both of our neighbors. And finally, things get interesting in the very, very last row, I contribute zero
3:26:22
to my neighbors, I contribute one to my neighbor, I contribute three to my neighbor. And at this point, we've kind of finished iterating through the entire grid. And if you look at this position, it contains a six symbolizing that, hey, how can you actually travel through a three by three grid? Well, there are actually six different ways you could do that. So before we jump into the code for this one, you can probably already foresee the complexity of
3:26:44
this. So we know that the complexity is really driven by the dimensions of this table, I know that this table is going to have m rows and n columns. So if I need to iterate through this table, it's just going to take m times n time. And along with that, what is the space that we need? Well, it's really just a space for this 2d array, which is, of course, still m by n. So overall have m times n time and space. Let's jump into the code for this one.
3:27:10
Now. All right back into the code editor. Let's work on implementing this grid traveller tabulation strategy. So we'll start by initializing our table, which is going to be a little more complex here compared to our last function, because it needs to be a 2d array. So what I'll do is I'll start by creating, let's say, the correct number of rows. So that will be as simple as calling array. And I want really dimensions m plus one, again, I have to adjust
3:27:36
for that off by one error, because I want the max index in this table to actually be exactly right. And I know indices start at zero, so I'm going to up it by one over here. Cool. So I'll give me the correct number of rows. And I want to make sure that the elements inside of this array are also other sub arrays. So a trick I can do for that is we're going to fill this is kind of just a very particular JavaScript pattern, I'm going to call fill
3:28:04
on this array I just created. And afterwards, I'm able to map over it. Cool. So maybe I'll spread this out like this. And when I map over this array, what I want to do is make sure that every element of the array is going to be a new array like this, this time of dimensions n plus one though, so I have roughly m rows and n columns. So let's go ahead and just see what the shape of this is. When I print out, let's say the three by two example. So we'll go ahead and
3:28:36
run this code. So notice that if I look at the arrays I printed out here, it looks like I have a four by three array, which makes sense because again, I increase my initial dimensions by one that looks good to go. However, what we'll want to do is really understand how what this map is useful for. So a very common mistake that you might be tempted to do is Can't I just, you know, skip this map part, and then do the fill with the array
3:29:07
of n plus one. So that will look like it gives you the same thing. So I'll run that code. But if you write it this way, what you're doing is you're filling the entire outer array with a single array instance multiple times, right? So the shortcoming of this code is let's say I kind of change only one position of the table, let's say I just made an X kind of arbitrarily, that would actually look like it changed many positions of the grid, right.
3:29:33
And that's because this is technically just one array that's inserted multiple times into the outer array, whereas I need a really unique array references. So that's how we need the map pattern here. I know every time we evaluate the callback function to map, it's actually going to execute this entire function, which means it's going to give us a new inner array instance. Right. So if I use this map pattern I run again, this is really the intended behavior,
3:30:00
right? I have a unique array as a sub arrays here. And so let's take out this expert. But that being said, Now that I have the correct shape of my table, I need to insert some good starting values, right? So what are the seed values here, while we're calling in our strategy, we said that basically the entire table could contain mostly zeros. So maybe I'll bake that right into this line. So after I make a new sub array, I'll be sure to fill it with some
3:30:32
zeros. So if I run that, now, I should have a nice table, because that's looking pretty good. At this point, I also need to see another value, right? We talked about it in that we should see table at position one, one with exactly one, this is sort of like our base case, when we have a one by one grid, there's definitely only one way to travel through it. So now we have the elements of one in position. One, one. Nice. So at this point,
3:31:00
now I need to iterate through my table and fill in other positions. So I'm going to use just nested loops for this. So I'll say let's i equal zero. And I want to make sure that I goes up to and including m right, basically the dimensions of the table, and I'll do i plus plus. And very similar for my inner loop being sure this time to reference j and j is gonna go up to n this time, because we'll just have classic nested loops just iterating
3:31:29
through this two dimensional array, right? So as I'm iterating through the table, what was the logic we trace through in our drawing? Well, I what I needed to do was take my current element that I'm at, so maybe I'll call it, let's say, my current. So my current element would be at table ij. So I need to take this current element, and I need to add it into my right neighbor, and my down neighbor, right. So if my row is I and my columns j, that just
3:32:00
means I do some arithmetic on i and j. Right. So if I want to increment my, let's say, right neighbor, what I can say is, look at table, a position i, j plus one, that'd be directly to my right. And I'm going to increase it by whatever this current is, if I want to look at my down neighbor, and that'd be i plus one, but I keep j the same. Cool. So this will add to my two neighbors that are to the right of me and below me. And at this
3:32:29
point, what we have to be aware of is like what happens at our edges of this table, we know that if we're already at like the last position of a row, if I do j plus one, I'm gonna go out of bounds. And so to make sure I don't step out of bounds on these increment expressions, I'll need some conditional logic. So I'll say if the right position is inbound, so if j plus one is less than or equal to n, then I'll go ahead and increment to the
3:32:56
end should be okay. And likewise, if i plus one is less than or equal to m, then I'll also increment right? Notice that when I checked my like j value, that should be using n, right, because that's the number of columns and then I is a number of rows. So it should use M. Cool. So what I have so far as I'm iterating through every position of my table, and I'm going to take the elements at my current position, and I'm going to add it into my right neighbor,
3:33:26
as well as my down neighbor, about only if they actually exist. Cool. So once I'm done filling up the table, then my final answer should just be at position m, and right just the very bottom right corner here. So let's give this code a run. So I should get 1336. And then there's a very large number, or run grid traveller. Nice and looks like this solution is totally working. And we are already satisfying our the last example here, right? If you tabulate off the bat, you will have a pretty quick
3:34:01
solution. And we already traced through the complexity for this. So take a moment to you know, look at this code, let it sink in, or really try to understand how we took that whiteboard strategy and implemented it in some code, right? We do have to do some like kind of fine implementation details, especially with the bounds checking here. But I think the most important logic, it's about how our current position of the table contributes
3:34:25
to our immediate neighbors to the right and downward. With that, I think let's head back into the drawing board. Alright, now that we've seen tabulation in two different problems, hopefully we're noticing some patterns right? Let's give ourselves some rules we can follow to tackle any dynamic programming problem using a general tabulation strategy. With this tabulation recipe, it's going to be pretty different compared to our memoization recipe
3:34:50
in that there aren't two main steps when I talked about memorization I said, make sure you implement the brute force first, and then add the memorization app. Towards. Whereas if you just try to tabulate a problem, you're really going to have the most efficient version of your solution all in one swoop. And so what is our first step for tabulation? Well, of course, you have to visualize it as a table. And that really begins with a conversation
3:35:16
of what you'd like the size or dimensions of the table V, that should definitely be correlated based on the size of the input. So in the case of fibonacci of n, we made our table roughly, you know, n elements long, sometimes you definitely have to watch out for like an off by one scenario, which we've been seeing lately. In the case of our grid traveler problem, we saw that because our, you know, problem represents a grid, we had
3:35:42
to create a two dimensional table at that. So figure out the size of your table based on the inputs to the problem. Cool. And once we do that, we need to initialize some values within the table. To me, this is always about choosing compatible types. In other words, if your problem asks you to return a number, then it'd be wise to initialize the values of your table with numbers right? On the flip side of that, if I was asked to return a Boolean
3:36:12
in a problem, Na, consider initializing true or false within the table. Cool. And once I have all of the kind of generic values filled up in the table, then I choose my very important seed value, right? I know that this seed value should capture the scenario, where I have a trivially small instance of the input where I automatically know the answer, right. So in the case of our classic Fibonacci, that means I just seed the N one and the N two
3:36:42
values of my table with one and one respectively. And in the case of our grid traveller, we were sure to capture the scenario where we had a one by one grid, so you're gonna need to see those values, because that's the basis upon which we fill the rest of the table. And then we have the hard part, which is really iterating through the table. And you have to come up with some logic, right, as you iterate through the table, you have to design
3:37:07
some logic that fills further positions of the table based on the current position. And you really have to, you know, look to the problem to figure out what the logic is. In the case of Fibonacci, it's as simple as if I'm at some position of the table, I look one space ahead and two spaces ahead, very reminiscent of the pattern Fibonacci, in the case of our grid traveler problem was about looking the unit to the right or the unit
3:37:30
downward, effectively shrinking the size of our grid. So it's really up to you to figure out the logic, look for it language in the problem. What I always do is focus on what options I have at any point in the problem, right? My options are Do I go rightward? Or do I go downward in that grid traveler and problem. So we'll stick to these rules as we tackle our a tabulation problems, and we'll utilize them right now.
3:37:59
Okay, so let's work on tabulating our can some problem now. So recall that in this problem we want to do is take in a target sum as an argument, as well as an array of numbers. And we want to return a Boolean indicating whether or not we could generate the target sum. By adding numbers in the array, we can reuse an element of the array as many times as we want, we can also assume that all the input numbers over here are non negative.
3:38:24
So we've solved this problem before, right? recursively using memoization. But now we want to use a tabulation point of view. So let's come up with the strategy here. So let's say I gave you this input of seven and an array of 534. In the long run, the answer is true because it is possible to generate seven, right, you can either do a three plus four or a four plus three, and that would give you your original target. So you know
3:38:47
that in the first step for tabulation, all we need to do is create a table. But I guess the question here is, what size table do I create, I have two inputs, I have the target as well as the array of numbers, which of those actually contribute to my initial table. And so the key insight is to think about, you know, what's going to change throughout the problem. In other words, if we can reuse the numbers of the array as many times as
3:39:09
we need, then it's not like we're shrinking the size of that array. However, if we think about the target number of the target, some that were given, we do have a goal of actually reaching that target. So now we're going to increase to it over time. And so I'm going to use that as a basis for my table. That is, I want to create an array that is roughly the size of my target sum. So because the target sum is seven, I want to make sure that
3:39:33
the indices lined up perfectly. So I'll actually have to create an array with length eight. And in general, I just be creating an array of length target sum plus one, because we have that classic off by one error over here. Alright, now that we have the correct size of table, what do I actually want to store inside? That is what should the eventual elements of this array be? So a really nice rule of thumb you can use for that is to just recognize
3:39:58
what type your answer should be. In the long run, right, so here, they're asking for a Boolean answer. So that really tells me that I should probably put some boolean data as the elements of this array. So I'm going to start by initializing every element of this array with a false value. And the reasoning is right now we're kind of assuming before we check anything, that none of these target sums are actually possible to be generated.
3:40:21
Cool. But neither think about any particular seed values, I need something inherent to this can some problem is we treat the target sum of zero very special, right sort of the base that we use. In other words, someone gave me a target of zero, I know that that is always possible, no matter what elements I have in the array, because to generate zero, I can just take no elements of the array. So that's going to be a really important seed
3:40:45
value here. So I'm going to populate index zero with the element. True. Cool. So now that we have some good seed value, now we want to think about how we can flesh out the other elements of this array, sort of in a linear fashion, right? So I'm gonna have to iterate through this table. So let's just start at the very first index. So right now I'm looking at index zero. And if I'm situated in any position of this array, then the value
3:41:12
I'm currently looking at, should basically say, you know, is it possible to generate that index amount? In other words, since I have a true at index zero, then I know that it is possible to generate zero using the coins of the array. But now that I'm at this position, how can I actually transition into the further positions of this table. And so what I want to do now is consider the possible numbers that I can take into my sum. So I'm
3:41:36
going to start by looking at this first element of five. I know that if it's possible to generate zero, then if I also have a five in the array, then it's also possible to generate five in the context of my array, that means I should look about five spaces ahead from my current position. So I look at this spot, right, exactly five indices ahead. And right, now I should actually replace this false value that's stored at index five, with a true and again, the
3:42:03
reasoning is, if it's possible to generate my current amount, right, right, I have a true in the zero, it's possible to generate my current amount, and I could take a five, that means that the position of five steps later should also be true, right. And I want to actually continue this process for the other values in my numbers array. So I'm just going to look at the next element of three, that's basically telling me that, hey, the
3:42:27
next spot three places away should also become a true, so I'll just go ahead and make that a true. And finally, likewise, for the last element of four, right, the element four spaces ahead, should also be turned to true. Cool. And at this point, I think I finished like my very, very first iteration, that is when my current is at index zero. And at this point, I just want to keep iterating through the array, so I'm just gonna shift my point of view, or one space to the right. So now
3:42:53
I'm looking at my current as index one. And what does that over here, my current element is actually false. So what that means is, it is not possible to generate one using the numbers of the array, which logically makes sense, right, I only have five, three and four. So there's no way you can ever give me back a one, right. So if I have a false value at my current position, then I should not modify like my further values by looking
3:43:19
ahead. So notice that if I look at my edge for five, look, five spaces ahead, I am not going to make that a true because my current position is not true, right. So I'm going to keep iterating. Same thing happens when I'm at index two, because the current value is false, there's nothing to be done here, things get really more interesting on this iteration right? at index three as my current, then I see a true at this position. So that
3:43:43
means I need to look ahead to my future positions, and actually assign them to be true. Obviously, you'll notice over here, if I look five positions ahead, when I'm currently at index three, then that would actually be out of bounds. So I don't need to look that far ahead. So we'll kind of drop that connection. But at this point, I should make the space three positions ahead truth, that's almost a space for positions ahead. So that means that indices
3:44:06
six and seven are set to true, right? I keep doing this process all the way through the entire table. Notice that as I keep iterating toward the right, these forward looking references kind of stopped being useful because it goes out of bounds. But the point is, by the end of all of these iterations, I do have a true stored at index seven, which means that it is possible not to generate a quantity of seven. And if I do a quick spot check, and
3:44:32
I look at just my entire table right now, it has very consistent data. In other words, if I notice where all of the true values are right there at 03456, and seven, that means that all of those quantities for target are actually possible, right? On the flip side, if I look at the only elements and indices that are false, like one and two, that makes sense, because those are the only quantities that are not possible or you can't possibly
3:44:55
generate a one and two, using a five, three and four as your option. Adding up, right? So we know by the end of this algorithm, the element that is stored at the last position of our table would be the final answer, right? So if it's true, then it's possible if it's false, it is definitely not possible. All right, so let's wrap up this sketch by actually talking about the complexity of this, as always, we'll define our terms. So we'll say that
3:45:20
n is going to be the target sum, which is just a number. And the flip side of that will say that n is going to be the length of the numbers array. And we already have the vibe that, hey, both of these terms definitely affect our complexity, right? If you give me a larger target sum, that's probably a harder thing to calculate. In the same way, if you give me more numbers to choose from, it's even harder to calculate, right. And
3:45:43
we can recognize that the algorithm just has us flesh out this table. And I know that the table is of size m, so we're going to have at least M. However, as I iterate through every position of the table, what I had to do was actually look ahead in the table for every single element of the numbers array. So I know that that's going to be accomplished basically, using some nested loops, where I'm going to have a loop to iterate through
3:46:07
just the table, and then a nested loop to iterate through every number of the numbers array. So overall, I'm looking at N, N times N, time complexity. And along with that, where does this space here? Well, the space is really just the exact size of this table, which is based solely on M. So I have just m space overall. Nice. So this is already looking like an efficient implementation, especially because we're not dabbling with any exponential
3:46:31
complexity over here. I think let's work on the code now. So here we are back in the code editor, let's start like we usually do by creating our table. So I'll store this table, and like we discussed in our drawing, we need to make it roughly the size of our target sum. So I'll create an array, I need to make sure that the indices lineup directly or at one index, that is exactly the target sum. So I'm going to initialize it to target sum
3:46:55
plus one, right. So that means if I pass in target sum is seven, when I create an array of length eight, which means that its very last index is seven, which is perfect. Cool. And while we're here, we'll go ahead and actually initialize this array with all false values. So I'll do that. I need to make sure that I seed index zero with a true symbolizing that the target sum is zero, it's always possible to be made, even before I look at, you know
3:47:23
what's in the numbers array. So I'll just go ahead and say, table at index zero is equal to true. So let's just console dot log, what this table looks like so far. And I'll just run, let's say the second example here. So I should see my array of length beat, up need to go into this tabulation folder. Now I'm going to run this guy. Cool. So it looks like a good table, right? eight elements. And I do have a true at index zero. Nice. So at this point, now
3:47:55
I want to actually lay out the core algorithm by iterating through the table, somebody who's a regular for loop here, let's say let i equals zero, go up to I can even include if I wanted to, up to an including the table dot length is you could also say a target some here some thing based on target some I'll do i plus plus. And here I'm going to choose to iterate using, you know the manual index, because I know I have to do some arithmetic to look
3:48:25
ahead on the array. But as I iterate through every element of the array, I want to actually check you know if this position is true, so I'll check if table at index AI is true. Cool, they know inside of this if statement, I need to basically jump ahead or look ahead, based on what's in my numbers array. But I only need to do that if my current position is true, right, I only got to look ahead, if it's even possible to get to this current
3:48:56
amount, right, the current amount I'm sort of tracing through would be at index i. So at this point inside of my if statement, what I want to do is now look ahead for each a number of this array, so a nested loop here. And I just want to look at the elements of this array. So I'll say for, let's say, let num of numbers. So I'm grabbing each element this time. And now for this number element, I want to look that many spaces ahead. So
3:49:25
I want to look at basically table at index i plus the number. Cool. So imagine that I'm on like the first iteration of this, I know is going to be zero. So that's the very, very first index of my table. And if my num is five, then I'm going to do zero plus five looking five spaces ahead right just like we did in our trace. And for this position, that is like five spaces ahead. I want to assign it to be true, basically saying that,
3:49:51
hey, if my current position is reachable, and I can take a step of exactly numb then that must mean position. I plus numb is also reachable write that entire for loop goes inside of this if statement, right? So this code is looking pretty good. So far, I think the last thing we need is just to return our final answer. After we're done iterating through the table. So here I'll just return table at index targets. Cool. So let's, let's go
3:50:24
ahead and run these examples. Maybe we'll have to debug some stuff. Looks like I have a probably an infinite loop. Yeah, my program crashed with some massive error. So let's debug this one together. There's something that I'm not considering in my code. But we did consider when we drew it out. So something that is probably breaking right now is having to do with like the bounds checking. Something that's kind of unfortunate in JavaScript is
3:50:50
this characteristic, this may have different behavior, depending on the programming language that you're following along in. But I know in JavaScript, I had some array, let's say, array, and I set it equal to just a handful of elements, let's say a, b, and c, if you actually do like array, at some out of bounds index, like index, I don't know 10. And I assign it like x, that will actually change like the effective length of this array. So
3:51:17
if I take a look at what happens here, so I'm just running this kind of offhand example, when we run this, notice that we have about seven empty items before we have the X. Basically, when you do this type of weird assignment in JavaScript, it's going to like lengthen your array. That way, it makes sure that this Hey, new element of x is placed at exactly index 10. And so why is that relevant? Well, in my code, here, I don't really check if
3:51:43
I'm out of bounds, right, and I just assign to something that's potentially outside of the current length of my array of my table, rather. And if I do that, then this condition is a little suspicious, right? Because if I do this assignment on line nine to an out of bounds position, then the length will get longer. And that's sort of like a circular argument, right? I keep iterating, only to make more stuff out of bounds, only to lengthen
3:52:07
the table even more. So that's why I ended up with like an infinite loop over here. One way I can fix that is to just maybe limit this, so I won't make a table outline that's a little too dynamic. I know, I can basically stop once I reach the targets. So that might actually be the better move over here. Pretty, pretty fair bug though. With that, let's go ahead and run this code again. give that a shot. Here we see true
3:52:35
true, false, true and false. And that is the correct answer over here. Nice. So here's a nice tabulated solution for our khamsum problem. And we already spoke about this code having n m times n, time complexity. Now it's really obvious, right? Because I can see how these exact the loops. And our space complexity is simply based off of M right. Cool. With that, let's head back into the drawing board for another problem. All right, now let's
3:53:04
work on the house some variation of this problem. So like before, I'm gonna take in the target some as well as an array of numbers. But this time around, what I want to do is return an array containing a combination of elements that actually adds up to the target sum. Right? So here, I want to return exactly one way if it's possible. And along with that, let's say that it's actually not possible to return the target sum, then I should just return
3:53:25
the null value. And if it's the case that there are actual multiple combinations that can generate the target sum, I can return any one of those. So we expect the strategy for this one to be very similar to our last problem. However, we will need some nuanced logic to return the array now, right? Because I don't want just boolean data once return an array. So let's sketch this one out. Let's see I'm stepping through this example. Or
3:53:47
my target is seven and my array is 534. For this input, a reasonable answer to return would be an array of three comma four, right? Because I can add three plus four to get seven. You can also I guess, switch around the order of these elements. So if you also returned four comma three, I think that would also be a valid answer. Point being, I just want to return at least one way that can generate the target. So we know we want to solve this
3:54:09
one with tabulation. And so we'll just follow our recipe right? And I need to construct an initialize some table, we already know that the size of this table is going to be based on the target sum, so roughly seven elements. But we of course, have that classic off by one nature, right? Because I want the last index of this table to align with the actual number argument. And in general, I'm going to initialize this array with a length
3:54:31
that is target sum plus one. Cool. So now that I have the correct shape of table, what do I actually have to initialize as elements inside of this table? Previously, like the Boolean version of this problem, we initialized everything as false, right. And the reasoning there was, before we actually try all the possibilities, we're going to just assume that it's not possible to generate every quantity. We just want to adapt that for this new type
3:54:56
of problem. They tell us that if it's not possible to generate amounts, then we should just return null. So I think null is actually a great initial value to just put everywhere in your table. So at the start, we're going to assume that none of the values or none of the amounts are actually possible to be generated. No is sort of the analog for false in this rendition. Cool. So now that I have most of the values
3:55:19
added to the table, now I need to figure out what's the appropriate seed value, I need some actual data to begin and get the ball rolling on this one. So like we expect, it's about having an amount of zero, right, no matter what if you're given an amount, or a target sum of zero, and no matter what array of numbers are given, you can always actually generate that quantity of zero, by just returning the empty array, right, you can take zero
3:55:42
elements from the numbers array, and there you have an array whose sum is zero. So of course, that means at index zero of our array, we're going to initialize it with just an empty array. And at this point, what we want to do is, of course, iterate through our table and come up with some logic we can use to fill out further positions to the table based on our current position. So let's say we begin at index zero. So here I am. And I have to
3:56:06
figure out which further positions of the table should I be looking at, we've seen this pattern before, I should just base that off of what I have as options in my numbers array. So look at my first number of five, that means I could look exactly five spaces ahead in the table at this position. And so if I know that my current position is possible, but I see that I have an array and my current position, I know it's possible. If this current
3:56:31
position is possible, then a position exactly five steps later would also be possible, right. And so what I'll do is I'm just going to copy my current value into my further value. In other words, I want to put an empty array at position five, right. However, I also have to include the number that I'm using right now, right, I took a five to actually get to this position in the first place. So I'm also going to add a five into that array.
3:57:00
Cool. If I do a quick spot check, this is a reasonable thing to do. Because if I look at the state of that index five, it contains an array of five, meaning that hey, you can return a sum of five by just taking a single five. And with this, I want to do the same logic for the other numbers of the numbers array, right. So if I have the three, I'll look three positions ahead of my current place. And I'll also start by copying over the array
3:57:25
at my current position. So I copy over the empty array. And after I copy that array, I actually want to populate it with the number that I took to get to the spot in the first place. So I just go ahead and put a three in that array. And the same thing happens for before. So if you go to the next iteration, you see that our current element is null, that means that the amount, right in other words, our index amount, is actually not possible, it's
3:57:50
not reachable, meaning we can't get an amount of one by adding up any numbers of the given array. So what I should not do is actually manipulate any further values from this position. So I just continue these base iterations. Same thing happens when I'm at index two, things get more interesting when I'm at index three, right, I see that the element here is not null. So it is possible to generate three. And so what I want to do is go ahead
3:58:16
and look at my my forward values, and for copy my current array over. So I know I don't need to look five spaces ahead, because that would be out of bounds. So I'm going to look at the position exactly three spaces ahead in the table and copy over my current array like this, what I also need to do is make sure that I include the number that I'm using right now, which is three, right, because I'm looking three spaces ahead. So I end up
3:58:40
with three comma three, at index six of my table, which is reasonable, right, I also want to do something very similar for the position four spaces ahead. So I'm going to copy over my current array, but then also include the four that I'm using up right now. So now have three four over here. Cool. At this point, you can kind of see where this is heading right, I've actually already populated index seven of my table, and three comma four
3:59:05
is exactly a one way we could create the seven. So we could stop here. However, let's say that you continued the algorithm. So in the next iteration, I know that this space for the indices ahead would be out of bounds, so I don't need to look there. But according to our general logic, I would actually manipulate the spot of the table three moves ahead, right. And so what I'll do is if I, you know, follow the same exact logic, I'm being consistent,
3:59:30
not really changing any of the rules here, I would copy over my current array into that position. So I basically overwrite index seven, with just an array of four. But then at this point, I would also be sure to include the number that I'm using right now, which is three, right, because I'm looking three spaces ahead. So I end up with four comma three, which happens to be like another way I can generate these seven. So it doesn't matter
3:59:53
if you actually continued this algorithm, right? So if I continued on basically just keep iterating until I hit the very And and what do I know the element at index seven is exactly an array of four, three. Cool. So the point is you actually don't have to like exit early. As you iterate through the table, you'll be okay to just finish all of your iterations. And you'd still have a valid answer, right? Because in this problem, they
4:00:17
just want any way to actually make the target. And if I take a quick look at my table, I think all of the stored values here make some logical sense. For example, if I look at index two, there's a null, meaning that it's not possible to make a two by using elements of the array. In a similar way, if I look at index four, there's a sub array of four, meaning you can just take one four, to make a some before. Similarly, you can take two threes
4:00:41
to make a sum of six. And of course, you can make a seven by doing four and three. So now that we have a plan of attack, let's look at the complexity for this. So of course, the M will represent the target sum, and our n represent the length of the numbers array. So if we begin with just the time complexity, we know that we're going to at least iterate through the table and the tables of size m, right. So I have at least an M in my time
4:01:06
complexity. But for every space in the table, or in every iteration of that loop, I need to also iterate through all of the numbers in my number input array. And so I can multiply by n over here. Nice. But at this point, now, let's say that I actually need to take a valid step here, then what I also did was copy over the array at my current position into that forward looking position, I know that a sub array will be at most of length m, remember
4:01:36
that m is our target amount, the worst possible or largest way we can generate the target sum would be to have an array of exactly m ones, right. And so we'll say that in the worst case, we have to copy over an array of an additional length m, that means our time is really m squared times. And now let's come up with the space complexity for this, we know that the initial size of the table is definitely based on M. However, in the
4:02:02
long run, we could be storing a sub arrays as elements. So this is going to actually be a 2d table. In a sense, I know that the size of any particular sub array here is also going to be m for the same reason we just said, and so we'd have a m squared space complexity. So overall, we're pretty satisfied with the complexity of this. Because it's polynomial, right? It's not an exponential quantity. So it should run in a reasonable amount of time.
4:02:27
All right, I think we're ready to hop into the code for this one. Alright, programmers back in my trusty editor, go ahead and tabulate this one out. So we'll need to create the table to begin, right. So I'll create my table, and it should have roughly targets some positions in it, really, I need to increase it by one. So I'll say array, and I'll pass in target sum plus one, that way the final index aligns, I'm going
4:02:51
to go ahead and fill this table up with all of those nulls. Right, exactly what we did in our drawing. What I also need to be sure to do is make sure we populate index zero of our table with an empty array serves as sort of like a base case, in that we know that the target sum of zero can always be generated, right, you can generate the target sum of zero by taking no elements from the numbers array, right? If you took the sum
4:03:16
of this array, it would be zero. Nice. This point, we need to iterate through our table. So you've seen this code before. I equals zero, go up to and I won't mess this up this time, I go up to an including target some I'll do i plus plus. So so far, very similar in shape to our last problem. Now that I'm iterating through every element of the table, I need to add some conditional logic. If you remember, from my drawing, we only did like
4:03:43
the heavy logic when our current position was not null, right? Because if it is no, you can't even reach this current position in the first place. So I'm going to check if my current amount is attainable. In other words, if table at index i, which is my current amount, if that is not know, if it's not know that I can generate amount I goal. So if I can generate amounts i that i know some other things could also be generated. That is, I
4:04:12
want to look forward in my table for every number in the numbers array. So I'll say let num of numbers, so I'm getting the elements of the numbers, right? And I need to look that number of positions ahead right. So if I'm at i right now, that means that a forward looking position would be at Table A plus num. Cool, and I need to assign something over here. So I'm going to do is start by copying over the sub array at position I at
4:04:43
my current position, right. I know that if table I is not know the only possibility that it could be is an array, right can be array of zero elements are going to be an array of many elements. So no matter what that array looks like, I'm just gonna copy over that array. So I'm going to spread out all of the elements table I. And so far like this logic is looking pretty good because I'm basing my assignment on table i plus num off of table
4:05:09
I, right. But in addition to that, I also need to include this choice of num. So I'm just going to add that into this new array as well using some syntax that we've seen previously in the course. Right. So I'm just copying over all the elements of the sub array at table I, and adding on an addition to that my current number. Nice. So this code is looking pretty good. I think at this point, all we need to do is let all these iterations finish,
4:05:35
and then wrap up by returning the last entry of the table, or really the table at index target some cool, so not that much different from our last piece of code. Let's give this a shot. So I'll run how some and here I have a few diverse examples. And notice that some of them should return null because they're not possible. If we check these 32243, no bunch of twos and another No, nice, it looks like this code is totally working. Notice
4:06:05
that we already have a very efficient algorithm kind of off the bat kind of comes free with tabulation, we definitely have m iterations in this for loop, we have n iterations on the inner loop. But then we also have to consider this copying over logic, right copying over an array will be at most m. So it's m times n times M, which is just m squared n, exactly how we spoke about it before. It's something I really want to emphasize is, you know, in
4:06:31
isolation, if someone just asked you to solve like this house on problem, I don't think it's an easy problem. However, it probably feels almost trivial, especially since we just did cancer, right? There's a really, really straightforward progression to these problems. If you compare the house some and can some functions, they're very, very similar, right, really just changing the type that we store inside of our table, as well as the
4:06:55
assignment that we do when we transition into our further elements of that table. Really just adjusting that logic for the data type that they're asking us for. Right? I had like some array answers here. And here, I have some Boolean answers. All right, so we're smashing through all of these tabulation exercises, let's do one more variation of this target some problem, that way, we'll have a little bit of an increase in the difficulty,
4:07:24
it's time to revisit the best sum problem. So we're going to take in again, the target sum as well as an array of numbers. But this time we want to do is return an array containing the shortest combination, that adds up to the target sum. And if we have any ties for the shortest combination, we can return any one of those shortest. So you take a look at an example kind of like we did before, we have eight and an array of 235, there are
4:07:46
a few different combinations, I can yield eight, right, I can do two plus two plus two plus two, or I can do two plus three plus three, or I can do three plus five. And among these options, the shortest one is obviously the three plus five. So that should be the return value over here. Obviously, if you returned five comma three, that would also be a valid answer. Nice. So let's start tackling this with our classic tabulation recipe. So
4:08:10
we need to decide on the size of our table, like we usually say it's going to be based on the target sum and not so much the length of the numbers array. And like we've been saying recently, it would be nice if the last index of a table aligns with the original target. So although the last index of this table is eight, that doesn't mean that its length would be nine, right? Let's start by setting the proper values here. I always want
4:08:33
to begin my my value seed with the type that's kind of relevant to this problem. In other words, they want us to always return an array if there is at least one valid way to generate the sum. And I know that trivially if I wanted to calculate the best sum for zero, no matter what array of numbers, I'm given the answer, there's always an empty array. So I'm going to be sure to store that value at index zero of my table. And now for the rest of the values
4:08:59
in the array, I can't be sure if I can generate them yet. So I'm going to initialize them as null just like our last problem. At this point, we can begin our general algorithm by iterating through the table. And so what I'll do now is look ahead for my current position based on the numbers of the numbers array. So I'm gonna look two spaces ahead. Right now I see that there's a no inside of that position, which means I haven't quite found
4:09:22
a way to create two, but I'm actually finding a way right now, right, I can copy over the array from my current position. But I also need to populate it with how far I'm looking ahead by so just to inside, and do this for the other numbers of the numbers array. So something similar happens for three, as well as for the five. Notice that since I just began the algorithm, this is a really the first time I'm finding any solution for these
4:09:46
further values. And so let's keep these iterations going. I'm going to shift my frame of reference by one since my current position, good things and all that kind of entails that one is unreachable, right have no way to generate a sum of one it's actually don't do any logic from this current position. So we move ahead to do, since I do have a non null value, right, I have an array over here, that means I should look ahead to my future values. So I start
4:10:12
by looking two spaces ahead, I see that at index four, there's a null, which means that I actually need to replace that now. Alright, I'm going to copy over my current array. But then I also add the value for how far I'm looking ahead by. So now I have two comma two inside of that index of four. So now I look ahead three spaces, which means I'm analyzing index five, I'll notice that index five already has an array there. And if I actually continue
4:10:39
my sort of standard process, I would consider this array, I would copy over my current array in yellow, which is an array of two, then I would also add the element I'm looking ahead by which is three. And technically two comma three is one of the ways I can generate five. But it's definitely not the shortest way right, I can basically compare the length of these arrays, and notice that the original array of just five is definitely shorter, so that
4:11:02
one should get the stay in this spot. Cool, I'll do something similar for five spaces, I see five spaces ahead for my current position yellow, there's a no right at index seven, which means that I can just go ahead and put this new array inside, so I copy over the array of two, then I add the five, right, because that's how far I'm looking ahead. I keep this process rolling, I'm going to modify two spaces ahead. Notice that this sub array I'm considering would still be longer than what's already
4:11:32
stored at index five. So I actually don't use the three comma to write the five gets the same. Now I look three spaces ahead. And this would actually be the first time I found at least a way to generate six. So I copy over my current array, and also add my lookahead value. And now if I look five spaces ahead, there's a Knoll currently in that index eight, which means that I'm actually finding the first way to generate eight, so I copy over
4:11:56
my array of three, and then I add my five for my look ahead. Cool. At this point, we've actually already found a way to generate eight. And you can probably foresee that this would be the shortest way in the long run. However, if we kind of continued this algorithm, there would actually be nothing wrong with continuing it right, it's not like we're ever going to put something longer in that spot. So if we continue our algorithm as normal, if I look
4:12:19
two spaces ahead for my current position, that would mean I'm considering two comma two comma two, to my array of three, three, and obviously, I just maintain the shorter one, so the three comma three gets to stay. If I look three spots ahead, then I would be comparing two comma two comma three to a two, five. And of course, the two, five is shorter, so it gets to stay. And this process really just continues for the rest of the array.
4:12:54
By the end of this algorithm, we do have the correct sub array stored at index eight. So before we jump into the code, let's look at the complexity of this one. So we'll say that MSR target's m, and n is the length of the numbers array. And so we know that in terms of the time complexity, it's going to be the same as last time, right? Still m squared times n, we don't really add any additional like costly logic, all we're really adding
4:13:18
into the mix is just some conditional logic, which I know is just a very simple if statement. So that's not going to add any additional time. And the same way, our space complexity is still m squared, right, because I have a table of size m. But I know every element of that table could be an array, really just a two dimensional array. I think with that, let's hop into the code for this. Back in the editor, let's go ahead and code this one
4:13:41
out. So we'll start by creating our table. And I'll make this table have roughly size of targets. But really target some plus one that way the final index aligns. And when I actually initialize this table, I want to actually make sure I have no values inside. So by default, all elements will be no basically symbolizing that, hey, these quantities cannot be generated yet, we have to actually prove that there is some combination that can make
4:14:09
them. But the really important seed value is to make sure that index zero is an empty array, right? Basically, the one guaranteed way I can make zero is by adding no numbers of the array. This point I need to iterate through every index of my table we always do. I'll go up to the end including why not the target some nice and as I iterate through every position of the table, I only need to do the heavy logic if my current position
4:14:41
is not no, right. So if my table and my current position so table I that is not no then I need to do some additional logic. So just to review, why do I need to only do the logic if my current position is not know? Well, let's say that it wasn't All right, if my current position is null, then I don't need to bother considering any further moves from this position if this position isn't reachable in the first place, right? So only if I have
4:15:10
a non null position, then I'll actually iterate through my options in the numbers array, or I'll consider possible moves. So let's say let num of numbers. And as I iterate through these additional numbers, and then I need to actually look ahead in the table basically by that number amount. So I need to write some logic about table at index i plus num, right, just looking forward in the table. And we know based on our previous problem,
4:15:38
it can some we ended up doing this logic, we just replaced that position with a new array, where we took all the elements from our current position, so table I, we spread out that array. Then we added additionally, this current number that we're using, right, so we have to actually add that into our move list. Cool. However, now we want to actually add some like, min value logic, I want to prefer to always keep the combination array
4:16:06
that is shorter, right, I want the best way, not just anyway. And so I think the move is or refactor this code a little bit. I'm going to actually do this step, maybe separately above. So I'm going to save this to a variable. And I'll call this my say, combination. This is like my candidate combination, I'm not sure if this one is actually the shortest right now. And so if I do the assignment over here, then I'll just use combination. But
4:16:34
I only want to do this assignment on line nine, if a condition is met, right, so what I want to express is, like, if this current combination is shorter, than what is already stored, right, I only get to replace something if it's shorter. That's pretty straightforward to express and an if statement, right? So I want to check, hey, if. And my condition needs to be if the thing already there. So if the element at index i plus num. If that
4:17:08
thing is actually bigger than my current combination, so combination, not length, and I also need to be sure to do that element dot length, right? If my combination is shorter than my current thing being stored in at that future position, then I'll go ahead and replace it. Nice. So this code is looking pretty good. There's one thing that's kind of missing, but I think we'll just run it and we'll kind of debug it together. So let's say at the
4:17:35
end, I return my table at index Parkinson. Cool. So compared to our last code, we only added this conditional logic. So if I run this, something's gonna go awry. And kind of foresee it's very an error. And the error message is pretty on the nose over here, it's saying, alright, cannot read property length of null. Right. So it's really about, particularly this expression. So we know that our initial state of the table has a bunch of null values.
4:18:08
So when I look ahead to a future value, and for the first time, I actually have a way to make it, then I'm going to check the element, which is no dot length, or I cannot do null dot length. Right. And so I need a way to kind of get around that. If ever, I have like a null value in my table, then I can just go ahead and do the assignment, right, because I found at least one way to make that. So what I'll say is I can put an order here.
4:18:33
So I can still do the assignment will say not table, i plus in JavaScript knows a falsie value. So let's say table at index i plus num is no. So this expression is no which is really false. So if I say not false and evaluates to true, so I'll go ahead and still assign that combination to that position, even if it isn't all, another great reason for using this syntaxes. We know toward like the tail end of our algorithm, we're going
4:19:03
to potentially look out of bounds, which means that these elements could be undefined and undefined is also a falsie value. Right? So here I'm saying not false, which triggers as true, which means I would still correctly assign those positions. Right. The important thing is I need to be sure to not do this expression. When the element is null or undefined. You can't say no dot length, and you also can't say undefined, not length. So this expression
4:19:33
will guard against that. So with that change, let's go ahead and run this. Cool. So 73544 and a bunch of 20 fives nice, especially looking at that last example, like 20 fives is obviously the best way to make 100. And just to be super Sure, should be no different if I even switched around the order of these sort of ways. So what I put like, one, five in two. That should still give me a bunch of 20 fives, right? Because it's really looking for the best way
4:20:08
to generate each some, which would mean the smallest summary. So there we have it a pretty interesting tabulation a problem. However, I do want us to recognize how similar it is to our last how some problem, right? So here, I have best some on the left and how some on the right, notice how similar the code is. Really, the only difference is this if statement, right? For the best some problem, I just added this conditional logic. And all
4:20:33
this does is prefer to keep the shorter combinations over the longer combinations, right, because that's what I want to return in the long run. Whereas in houssam, we don't really have any preference in either direction. Awesome. So let's go ahead and go back to the drawing board, I think we'll kind of switch things up. Let's switch gears a little bit and revisit those string problems with tabulation. Let's begin with that can construct problem. So
4:20:57
we're going to take in a target string as well as an array of words in a word bank. And this version of the problem and I want to do is return a Boolean, right, true or false, indicating whether or not I can make the target by concatenating, any number of elements from the word bank array, and I can reuse elements in the word bank as many times as I want. So we've seen this problem before. But just to refresh, let's take a look at
4:21:17
an example. So let's say my target was abcdef. And I gave you this array of some different substrings. In this particular scenario, it is possible to create abcdef using members of the array. So the answer here is true. And one way you can actually create your target string is by just doing ABC plus the fright. Alright, let's start to apply our tabulation to this one. So I'm going to create a table and you probably already recognize that, why
4:21:44
I want to base the size of this table off of the target string, right, because that's really where I have some problems, I'm going to be decreasing the size of my target, or in other words, building up to my original target over time. And so I know that I'm going to make it about the target string and not the array of words, because I'm never going to remove a word out of the word bank. So I'm gonna start with this table. And here
4:22:07
the sizing is is kind of particular, because we need a way to have this table or represent information of a string, right. Whereas before with our number problems, it's very straightforward to just use the index as the actual number. So we're going to use a little clever have an encoding here. And so what you'll notice is here, I created an array of size seven, right, table dot length is seven right now. And in general, you'll want to size your table
4:22:35
by doing target dot length plus one. So we still have that sort of off by one scenario, that's kind of a very characteristic of these tabulation problems. And so what will this table represent? Well, if I just think of the characters of my original target string, I know they have corresponding indices sort of like this, you're probably wondering, then what's the point of having that extra spot at the very end of the array,
4:23:00
right? What I need to store index six, if it has no corresponding character. And the reasoning is, we need a way to actually represent information about the empty string. And so here's the pattern we're going to use. If I look at index zero of this table, then I'm actually making a statement about the empty string. So pretend that if you look at a spots of this table, depending on what that index is, you're considering the substring, that
4:23:27
starts at index zero, and goes up to but not including your current position. So we'll see how this scales over the rest of the indices here. So imagine that now is at index one, I'm looking at index one, and you're really just looking at the A string, for at index two, then you're looking at a B, if you're at index three, then you're looking at ABC, for index four, then you're going A through D, if you're at index five, you're looking
4:23:52
at A through E. And so the really key insight here is if I'm looking at index five of my table, it means I'm making some logical statement about the substring starting from index zero going up to but not including index five, right? So if I wanted to make a statement about the entire target string, then I should actually look at index six, right? Because imagine you start your substring at index zero always, and you go up to but not including
4:24:19
your current index. And again, the whole reason for this is I need a way to actually make a statement about the empty string. And so speaking of the empty string, let's go ahead and talk about our C values. We know that a really core you know pattern in this can construct problem is to use the fact that hey, if your target string was empty, no matter what array of words you were given in your word bank, that is always possible. So it's always true. And so that means at index zero
4:24:48
of my table, I can go ahead and seed a boolean value. How do I know what type to even store as the elements of my table? Well, if the problem is asking me to return a Boolean, then it's probably a good To actually just begin with some boolean data in your table. So if index zero is going to start as true, I'm going to initialize the rest to be false, right. So I'm going to consider all of these other sub strings or prefixes as not possible
4:25:12
until I prove them otherwise. Alright, so let's begin our general algorithm. So we'll begin like we always do by just iterating, from left to right through our table. And just we have some notation to make it easier to kind of translate the information in a table to the statement it makes about our target string, I'm going to have the characters up top, and I'm going to like them up based on the substrings that we're really considering
4:25:33
here. So if I begin at index zero, like we said before, that means I'm making a statement about the empty string, right, I see a true inside of this position, which entails that the empty string can be constructed using the word bank. Cool. At this point, I have to figure out how I can look ahead to my further values in the table. And I know that I can do that based on the choice of words in the word bank. So let's look at one of our words
4:26:00
like a B. So something great about this option of a B is it actually is something that begins from my current position, right. In other words, if you look at my current position in yellow, the characters below it start with a and follows with me. So taking an AB right now would be a totally legal move, right those characters align. And so what I'll do is, I'll go ahead and look two characters ahead, by look two characters ahead in my table,
4:26:26
that just means look two indices ahead. So now I know that this position of the table is actually reachable by just taking a B. So I put a true here. And now at this point, I would do this same logic for the other words that have their characters aligned. In other words, ABC is also some matching word. So I'll go ahead and make that a true. And ABCD would be the only other one that actually aligned its characters. So I'll make that
4:26:49
one true. Again, how do I know to actually put this information in the table, it's really just the length of the word right, my current position right now is at index zero. And I'm looking at a word that is four characters long. So that means I just look for characters ahead to store my Boolean. Cool at this point, I'm actually done looking at all the words for this current position. So now I can move my current ahead one. So now I'm at this position.
4:27:15
And so what you'll notice is in this current position at index one, we have the value of f, which means that it's false, right? It is not possible to actually generate in a write, there's no way you can ever just give me back an A, because all of your substrings in the word bank are too long, right? So I don't actually need to do any of my heavy logic from this position. However, on the next iteration, when I have something that's
4:27:40
true, then I need to do my heavy logic. And if I do a quick spot check, I have a true stored in this position to write if I'm looking at the value stored at index two, that means I'm making some statement about indices zero up to but not including tomb. So really just the substring AB. And I know that if it's true, that means it's possible. And looking at the elements of the array, it's definitely possible, right? You just took a beat even
4:28:03
get to this position. But I need to look ahead. So I'm going to look at any words of the word bank that match starting from my current position. Really, the only option here is CD, right. So if you look at my going characters, right now, that means I can take this CD. And so what I'll do is I'll look two characters ahead and place a value at that position. That's true. But the value stored at this position of the table is already true. So nothing really
4:28:30
changes here. And there are no other words of the word bank that actually begin with a C. So I'm actually done with this pass. So now I move my current again. And I look for any matching words that begin with like a D, and potentially other characters after that, really, the only one here that works out is D, F. And so looking at my going characters, now I'm basically considering this chunk, right ABC followed by TF. So I'm going to
4:28:56
look three positions ahead, because the word I'm considering right now is three characters, right def is just three characters. If I do that, I'd be looking at this position. And I'd be making this one a true now basically saying that it is possible to construct abcdef colon at this point, I would do the same thing for the rest of the table, we know that nothing else is really going to change within this table.
4:29:20
And so by the end of the algorithm, we have a true start at index six, which means that our entire string is possible to be constructed. Right? And so if we do a quick sanity check, if I look at the table at index six, that means I'm making some statement about the substring that starts at zero and goes up to but not including index six, which would really be the entire A through F. I know that it's true. So that substring is possible to
4:29:47
be generated, right, which was our final answer fairly elsewhere. Like maybe at index five, there's a false here, which means that I'm making some statement about indices zero through four, right, so ABS C, D E. And since there's a false at this position, that means that it's not possible to generate this string. And looking at just the elements of the word bank, it's definitely not possible to ever get a, b, c, d, e. Cool. So the data within
4:30:13
our table a does look consistent with that, let's actually talk about the complexity. So we know that m is going to be our target string, whereas n is going to be the number of words in the word bank. And so we just consider the time complexity right now, we know that we're at least iterating through every element of our table, and our table was roughly size M, right? However, once we were at some current position of a table,
4:30:39
we had to look ahead based on all of the words in the word bank. And so that would be an N operation for every iteration of m. And even still, as always, considering the words coming from my current position. And to make sure that their characters aligned, right, I can't just take arbitrary words, from the word bank, I have to choose the ones that have their characters matching right now, I know that the maximum length of any word
4:31:03
or the maximal length of a match, I would have to do would basically just be in terms of M, so give me an additional m term. So overall, I'm looking at m squared n for the time complexity of this one. And besides that, we already know that the space complexity comes from the table, which is just a array of Boolean, so just m space overall. And so from a bird's eye view, it looks like this strategy would be an efficient one, right,
4:31:27
we have a polynomial time complexity, but more importantly, a non exponential complexity. So let's code this one up now. Alright, let's code up this can construct problem. So we'll start by creating our table. And so we'll say create a new array of size target dot length, plus one just like we spoke about in our drawing, then from there, I need to give some initial values to my table. So I'm going to go ahead and fill this one up with
4:31:53
all falses. So we're going to assume that every like prefix of our target cannot be constructed until we prove it otherwise, then I need to actually also initialize table index zero to be true, symbolizing that the empty string can always be generated, right? Then from there, I need to iterate through every index of my table. So I'll say i equals zero, just go up to the entire table. And here just to be safe, I'll say is less than or equal
4:32:20
to target dot length. Nice. And as we iterate, we actually need to check our current positions value. Recall that in our strategy, we said we only need to do like the heavy logic, if our current position is reachable, so our current position should be true. So I'm gonna go ahead and check Hey, if my table at index i is true, then I'll do some additional logic. If I enter this if statement that I need to consider any further choice of words I can
4:32:55
use to progress to other spots in the array, right? So over here in this if statement, I want to iterate through every word of the word bank, right? So I'll say four letter word of word bank. Nice. And so what I want to do, as I iterate through all my possible words is I need to make sure that these words I iterate through actually match their characters to my current spot that I'm at. In other words, if I am at my very first index of a over here,
4:33:29
then when I iterate through all the options of words, I need to make sure that I only use a valid words that match like a, b, or ABC, or ABCD. Right? There's no point of me trying to use def right now. Right? I need to actually kind of narrow down my words, based on whether or not they match characters, right. So to do that, I can check pay if. And what I want to express is, you know, if the word matches the characters, starting at position, I
4:34:00
position I goal, it's not going to translate that into some code. Well, checking if a string matches to something straightforward, just about using equality, right? But I have to figure out how can I look at the correct you know, substring of characters within my original target, right? It's pretty straightforward. All I need to do is say target dot slice. I'm going to slice starting at index i. And how far do I want to go? I basically want
4:34:29
to go like the length of my word. So the move here is to say go from I up to i plus word dot length. And so let's kind of break down this logic. So what it's trying to do is check if your word matches your characters starting at position I. So let's check an easiest scenario. Let's say that my current position is zero, right? So right now is zero. That means I'm at this position like this ABCD f example. Let's say right now that my word is ABC. So
4:35:00
if I look at this slice, it's going to slice starting at index zero, up to and not including zero plus three, right, the length of my word is three, zero plus three is just three, that would actually look at this run of ABC. Good. And let's say we were somewhere further in the string. Let's say we were actually at this D character over here. And so if I'm at this D character, that means my value for AI is going to be three Wragge, oh 0123. And
4:35:30
the current word I'm considering, let's say is this def, the length of this word is three. So this ending index is going to be three plus three, which is six. And so I would actually slice starting at this character, three, going all the way through the end, right? 345. And I always exclude the ending index of six here. So this logic is good, right? All it does is check if my current word matches the characters starting at index i, goal. So if I enter this
4:35:57
if statement, then I have a successful word. So I should actually set a true in that forward looking position. So I can just set table. And when I look ahead, how far do I need to look? Well, you need to look exactly this far ahead, right, i plus word dot length, matching me we're at index zero of our target string. If I take ABC, then I end up word dot length characters later, three characters later in this example, right. So I'm saying
4:36:23
table of i plus word dot length, that should be set to true. Cool, notice how similar This is to our previous number, like our target some problems, except now we have to adapt this four string data. So now I jump ahead based on the length of the word I'm choosing. So this code is looking pretty good. Let's go ahead and do our final return value. So I want to return the table at Target dot length, right? Basically, if I'm at the last position,
4:36:53
or at Target length, a position of my table, that means I have the information for the entire target range starting at index zero all the way through the end of the target. So here are some examples. Let's give this a run. So I get true, false, true, false. Nice, and there we have a nice working solution. So take a moment to let this code sink. And really the most tedious logic here is probably this particular slice. So really try to make
4:37:24
sure you kind of understand how this comment is implemented using this code. If you remember our previous recursive immobilization strategy for this problem, we needed to actually have logic to make sure our prefixes match. This is sort of the analog for that, right. So we already spoke about the time complexity for this one, but it's already in plain sight, right, we have m iterations here, we have n iterations here. And then the additional
4:37:49
work we do is this slice, right, I'm slicing from my target, which is also M. So overall, I have m times n times m, or m squared, N. And of course, the table just takes up definitely m space. Cool. So with that, let's head back into the drawing board. All right, now let's revisit the count construct problem. So we're still going to take in a target string as well as an array of words in a word bank. And this time, we want to return a number,
4:38:15
right, we want to turn the number of ways that the target can be created by concatenating elements of that word bank, we can reuse elements of the word bank as many times as we want. So let's take a look at an example of this. So let's say I had this input, so I have the target of purple, and I have an array with some substrings. The return value here should be two because they are exactly two ways to create purple. You can do perp plus le, or
4:38:38
you can do p plus u r plus p plus le ran, those are two distinct ways. So notice in this problem, we really just want to return to the numbers. So we'll just keep that in mind. So let's follow that classic tabulation recipe, we'll initialize our table with roughly the size of the input that changes, which is really going to be the target string, right, we want to actually use overlapping subproblems on the target string.
4:39:01
And like we always say, we're going to have a little off by one scenario here. Although the number of characters in my purple string is six, I want to initialize a table of length seven. In general, you want to make sure your table has target dot length plus one a number of elements inside. That way, I have a way to represent the empty string, just like our last tabulation. And so we'll start by thinking about what are some proper seed values for
4:39:25
this problem. I know that when I have an empty string, empty target strings, my input, no matter what array I'm given, you can always generate the empty string right by taking no elements of the word bank. So the answer for the target string should be one, right, there's one way to make the target string and that is to concatenate nothing together. So I'm going to store the value of one at index zero of my table. Now I have to decide
4:39:48
how to initialize the other values in my table. Well, I know that it should be number data, right? It's really important that you try your best to make your table contain a consistent data type. If I remember my similar counting problems like Fibonacci, or even the grid traveller of the move here is actually start those other spots in the array at zero, basically saying, you know, at the start, I have zero ways to generate these different prefixes
4:40:12
of purple. And then as to actually find distinct ways, I'll go ahead and increment those spots in the table. But we'll get to that. So we'll iterate through our table from left to right, of course, beginning at index zero of the table. And as we do this, I'll also up top show the characters that we're considering within our table. Remember, the really important pattern here is when I'm at some position of my table, that means I'm encoding some
4:40:39
information about the substring that starts index zero, up to but not including my current index, right. So if I have some information stored at index zero, that information is about the empty string. From my current position. Now I need to consider any words of the word bank that I can take right now to give me another spot within the table. In other words, since I'm at index zero, I need words that start with P. So let's say we looked at this
4:41:03
first word of perp. And so if I looked at that word, and I took it, that would bring me a somewhere else within the table, right have to look forward like we usually do. So they'll end up at this position index four. Again, notice that we have the kind of off by one scenario here. So although I'm going to write information into index four, that informations about the substring, that spans from zero, up through index three, right,
4:41:27
and what I need to do now is take my current value in yellow, actually add that into my future position. So I just add one into the zero. And now index four contains a one, right basically saying that so far, we found a one way to construct the string perp. And then from there, I look at any other words that the word bank that match right, so I'll just look at the next word of P. Again, just moving left to right through our word bank, right
4:41:51
now, I'm still at my current position. And what I do if I use this P is I only look one character ahead, right, because p dot length is only one. What I do in this future position is of course, just take my current value in yellow, and I added into this position, so zero plus one is just a one. There is one more word I can use right now from my current position, that's purple without the E. And if I look at that corresponding position,
4:42:18
they'll bring me all the way over here. And again, I add the one into that position. Nice, I think that ends are a very first pass. And now we move our current position to the right. So now my current is at index one. So now I need to consider words of the word bank that begin with a you and kind of match characters throughout. The only option here is really just you are in the word bank, if I took a u r, that would bring me two characters ahead,
4:42:43
right, so bring me over here, what I should do like always, is just take my current value and add it into that position. Now I have a one over here. There are actually no other words of the word bank that match from my current location. So I can just move ahead to the next spot in the table. If we're at index two, it looks like we need something that starts with an R, there's actually no words of the word bank that we can use from
4:43:05
this position. And what we also notice is there's also a zero at this opposition. So this won't really do anything in our table anyway. So we can progress just the next spot in the table. Here's where things start to get interesting, right? So right now my current is at index three. So I need to grab words from the word bank that start with P and potentially have an L enemy. So what I can do here is just take this loan p, which will bring me
4:43:31
one character ahead. If I look one character ahead, what I do now is I take my current value, right circled in yellow, and I add it into my look at value. So I increment that to two now. Nice. And then from there, I need to continue on my logic by just moving rightward in my table, right shift my current point of view. At this point, what I do is I again, look at any words that start with an le, and there's really only one that matches perfectly, I look two characters head because the length
4:44:01
of Le is two. And what I do is I take my current value in yellow, and add it into that position, right, my logic throughout this entire algorithm is very consistent. And there we have a two in the last spot, you can probably already foresee that we have our final answer. But if we continue the algorithm as normal, or really, we've noticed that if we move to the next position, there's no word of the word that starts with E. So I don't do anything
4:44:22
here. And once we hit the very end, we're actually done with our algorithm. Right? And we see that, hey, we have a two in the last spot a retailer which is consistent with our expected answer. Something I think is really important to do is not only recognize that our final answer is in the last position of the table, but really any element of this table should make some logical statement about our target string, right? So let's say I look
4:44:47
at index for over here. I see that there's a two in that spot in the array. So what does that really saying? Well, if I am looking at the value stored at index four, that means I'm considering the substring That starts at zero and goes up to including four. So that really means I'm looking at purp, right. And if there's a two inside of the spot in the array, that means that there are apparently two ways to create perp. And if I do a quick
4:45:13
check in my word bank, that's exactly true, right, you can just take the straight up perk, because that's actually a literal word of your word bank. Or you can do p plus u r plus P. Cool. That's some consistent information. And then from there, if I actually consider now what I can do from that position at index four, well, you could have taken an le, that's basically what we did when we traced through the algorithm. If you take an le, what are
4:45:37
you really doing? Why is that value in the index six, also two? Well, for one, Ellie has a length of two. So that's why I'm looking just two spaces ahead in my table. And if I think about what like logical operation I'm doing, if I were to take an L e, and add it to all of the ways that I have in blue Rhino, then I would end up with all of the ways to generate purple right in my last spot, literally just taking the Le as an additional
4:46:04
move, right? Pretty elegant logic. Let's talk about the time complexity for this though. So we know that, hey, r m is going to be the target and n is going to be the number of words in the word bank, this is really going to be about the same complexity as our last rendition, right? You can't construct. So we're gonna have m squared times n time, right, we definitely have m time for just iterating through every spot of the array. And we also
4:46:30
have an additional n, because we have to actually look forward for every element of the word bank. And so where does that final m come from? Like we've been saying lately, it comes from actually performing the match of the check for matching characters. In a similar way, the space complexity is just going to be m, really just based off of the size of the table, we're only ever storing just some numbers within this table. So our space just
4:46:55
stays at linear o of M space. All right, I'm feeling good about this plan, time to code it up. Alright, let's code this one out. Let's start by creating my table, it's gonna begin as an array with roughly target length, size, really target length plus one, that way the index aligns, right, I'm going to fill this entire table with zeros for now, because I know in the long run, I'm going to add into it. So zero is a great starting value. That
4:47:23
being said, I have a really important c value, I need to make sure that my table at index zero actually starts as one, right, because there is one way to make the empty string right. Now from here, I can start my core algorithm by just iterating through every position of the table. So set i equal to zero, go up to an including target dot length, and hit every index, right. And so what I'll do is iterate through every word of the word bank. So let's word of word bank.
4:47:55
And as I iterate through every word, I need to check if the word matches my current location right there has aligning characters. So you've seen this pattern before, I'll check if target that slice I'm gonna slice some characters out of my target. Starting index i right, this is my current position, I need to look at the next couple of characters based on the length of my word, I'm going to slice i to i plus word dot length. goal. So my current
4:48:23
position is I, this will give me the next word dot length number of characters starting at position, I will check if that little segment is equal to the word I'm considering right now. And if it is equal, then I have a word that I can actually take, I can modify some further position of the table. In particular, what I should do is need to modify my table at index i plus word dot length. So I'm looking to head remember that our current position
4:48:50
is I so I'm looking ahead in the table based on my current words length, what I want to do is actually increase that by some value, want to increase it by the number stored in my current position, right? That's what we did at every point of the algorithm. Nice. A common mistake that I see students make is, usually they have a tendency to just increment by one here, right? That's not the move Do you want to do is increment by exactly the
4:49:16
number that's in your current position, right. Now, at this point, I think all we need to do is just return our final answer, which like we always know, is basically table at Target dot length. Cool, so I have some examples below. With their expected results, let's give this a shot count construct. So I get to 104 and zero, that's that we have a fairly large example, which should return zero, you can't possibly generate this final f here,
4:49:45
because your word bank only contains a bunch of E's, and it ran fairly quick. So this solution is looking pretty good. Notice how small of a variation it is from our last problem. Hopefully you're really feeling the progression. So let's kind of quickly just take a look at That that was our can construct problem. So let me split these guys. Very, very trivial difference, right, instead of assigning a true value. Now I actually just increment
4:50:14
because I have numbers within my table. That was short and sweet. Let's head back into the drawing board. Let's do one more problem together, let's revisit that all construct problem. So we're still taking in our target string, as well as an array of words in a word bank. But this time, you want to return all of the ways that you could construct the target by concatenating elements of the word bank. So here, you need to return a 2d array,
4:50:39
that means a single element of the array represents a one combination that makes it a target. And like usual, we can reuse elements of the word bank as many times as we see fit. So we take a look at an example, let's say I gave you the target of abcdef, I gave you this array of words, you actually have many ways to create the target string, there are four ways over here. So each sub array represents one combination, where if you concatenate
4:51:04
it together, you get the target. And so notice that I want to return every single combination as an element of the outer array over here, right. So if there are many ways to create something, then I want to return a 2d array. That being said, there are a few examples that we should keep really in mind having to do with our seed values that we kind of foresee. Right. So let's say I gave you this example, where your target is the empty string,
4:51:27
and I gave you just some words in the word bank. The point is, since your target string is empty, your result should really be a 2d, empty array. So recall that the outer array here represents like the collection of multiple combinations. And here, there's only one combination that makes the empty string, right, so the inner array represents like that empty combination, we take no words of the word bank. And this is a reasonable thing to do, because they'll
4:51:54
take give you this example, if your target was birds, and I gave you an array of cat and dog, then the result, there should be just a one dimensional empty array, right? The array over here represents the collection of combinations. And there are no elements here, right? There are no combinations at every yield of birds. So we'll keep those sort of seed value base case scenarios in mind. So let's trace through this example
4:52:19
of abcdef. I'll start by initializing our table, we're gonna need a lot of room in this one. And so we know that the size of this table is going to be based on the target string, right, just like we usually do. And then we have to figure out what our seed values are, we kind of just spoke about them, we know that if I have the empty string, then I need to have a 2d empty array. And so we'll initialize that in our table,
4:52:44
I know we're going to need a lot of room. So I'm going to spread out these outer brackets. Now for all of the other elements of our table, we want to make them just one dimensional empty arrays. And here's the reason why I write for these further values in the table, I have to actually check for ways to generate them. So for now, there are no ways that I found right, that's why I just have an array with zero combinations inside, except for
4:53:11
index zero, right? index zero has one combination inside, that happens to be the empty combination. Cool. So let's start with our general algorithm. A lot of this logic will feel very similar to our last few problems. Now we're just adjusting it have to generate these combinations, right. So we know that we're going to try to visualize how we look at our string in terms of some prefixes, right. I know that if I'm highlighting some spot in my table, then that grabs the
4:53:37
prefix or an index zero all the way up to midnight, including my current index of the table. And I'll light up those characters at the top over here. So what I need to do now is since I'm currently at index zero of my table, I consider words of my word bank that have matching characters from this position. So I can look at this a B First, if I took this A B move, then I should look two characters ahead, right, because a B has a length of
4:54:01
two. So that brings me to this position in light blue. And what I should do is take all of the combinations in my current location in yellow, and actually copy them over into this future position. But when I do that, I also need to be sure to include in those combinations, the move of the word I just took, right, so that would just be adding an AB inside. Right. So again, kind of repeating that step, I copy over the contents of my
4:54:27
current position in yellow. But then I have to make sure I add my word that I'm consuming right now into each of those combinations I just added. Cool. And now we would actually keep our current position here because there are still some other words of the word bank that have matching characters, right, I can take an ABC from this position, and something very similar happens write a copy over my current array. And then I go ahead and add ABC to it. This happens one more time for ABCD
4:54:56
Awesome. At this point, I've considered all of the words that match from this current position. So I can move forward a little bit. At this point, though, I need something that starts with A, B, right? Because my current position has to be on it. And I actually don't find any words of the word bank, that kind of match from this position. So I actually moved my current once more. What about this position, I have to consider words of the
4:55:27
word bank that have a seat, right, and there are a few that can use here, I can use CD, right. And if I do that, I look two characters ahead or two indices ahead for my current position. So I'm looking at this index. So if I look at index four, I have a really interesting situation, right? I already have a some combination stored inside of index four. And that represents one way we could make ABCD, right by just taking that loanword ABCD. But what I can
4:55:53
also do is, I should take all of the combinations from my current position and just add them into that index for right, so I'm taking the A B from index two, just adding it to index four. But then I also need to add to that new combination of the word I'm using right now, which was CD. Cool. And then from here, you already noticed that, hey, there are so far, two ways to create ABCD, you can just take that loan word ABCD. Or you can do a
4:56:20
B plus CD. So this logic is taking some some nice shape here. For my current position, there's actually one more word that matches, it's really just a single character see, so like I do, I look one character head or one index head in my table just next door, and I copy over the combinations from my current location in yellow. But then I also append the word I'm consuming, which is just an additional C, right. So so far, I have two ways to make
4:56:45
ABC. At this point, I can progress my current spot and table. And I look for any matching words that start with a D, right? So that would be the D f over here. d f has a length of three. So I look three spots ahead in my table. And I need to add some information here, I copy over my current combinations in yellow. And then I have to append at the end of all of them the D F word that I'm using right now. So it looks like this. At this
4:57:15
point, I can iterate my current position. So now I'm at index four as my current. And I look at any words that start with any, and there's actually just one over here just as EF. And so I look to character's head or to indices ahead for my current position. And again, this is a scenario where I need to append new combinations to this existing list, right. So if I look at my current position at index four in yellow, I'm going to take
4:57:37
all of those combinations and copy them over into my light blue position at index six. And then from there, I also need to make sure that I append to them the word I'm using right now, which is an E, F. So those two combinations also get an F at the end of them. Nice. At this point, you see our final results at the last spot on the table, we continue the general algorithm, we would just move our current position to index five, which is actually
4:58:03
a no words of x star with an F over here. So nothing happens on this iteration. And there we have our algorithm, right, that index six of the table contains all of those four ways we described how we can use to create our original target string, take a moment to look at this table. And notice how every position of the table should make some logical statement about the target string. Right, I can see that if I chose some position, let's
4:58:31
say index three, that's giving me some information about the substring ABC, right, that prefix of my original target. And what saying is, there are two ways to make ABC, you can just take ABC, that's actually a word of my word bank. Or you can do a B plus C, right? That's the only other way that applies for all positions within my table. If I look somewhere else, like at index five, that means I'm reading some information about A through E. And if
4:58:59
there's no combinations at this position, means there's no way you can ever generate ABCDE. And if you take a quick glance at the words in the word bank, that is correct, you can't possibly just generate ABCD. Overall, the information in our table and our logic that we did was very consistent. Before we hop into the code for this one, let's do the analysis. So we know that m is going to be the length of our target string. And we'll
4:59:24
define n to be the number of words in the word bank. So like we described, when we did the memorization and recursive solution for this problem, we really can't do better than a sort of brute force, right? Because they're asking us to return literally every single way to generate our target string here. So really, the time complexity is going to be the shape of an exponential, right, so about n to the M, again, it will have some extra like multiplication terms of M
4:59:52
in it. But overall, we're looking at an exponential time complexity. And what's the reason behind that? Well, we know there's going to be an exponent The number of actual combinations that we need to return. And I have to actually construct all of those combinations piece by piece. And so I'm looking at at least exponential time. And really, once something gets exponential, that's really the limiting factor, right. And similarly, we can say that the space complexity
5:00:19
for this is also going to be exponential. Again, roughly, we know that we're going to have at least m space just from the straightforward sides of the table. But notice that every element of the table itself is going to be a 2d array. So in a sense, we're really dealing with like a 3d table in this instance. And so we know that at any particular position of our table, we're going to have potentially an exponential number of things, right, if
5:00:46
you consider the very last spot in our table, just the last spot that already has an exponential number of combinations inside of it, but then I would actually have that throughout my entire table, so it'd be really a little more than just n to the M. But overall, I'll say it's roughly exponential complexity. And you can't really do any better here, right, especially in terms of the time, I'm really asking you to just do this in a brute force way, I think
5:01:12
we'll actually be able to see that once we create the solution. Let's hop into it. Alright, for one last time, let's solve this all construct problem. So I'll begin by creating my table. By now we're tabulation masters, this is very, very formulaic. Create my table with roughly target size really target dot length plus one. And here, I need to initialize the elements of my table as arrays. So here, I need to be very particular and make sure I get a unique
5:01:40
array in every spot of the array. So I'm going to do a fill using this index before, then I'll map over it that way I can generate a new array for every element here. Cool, let me just style this up. And so this should give me an array as every element of my table, right? Notice that the elements right now are just one dimensional empty arrays, right? These arrays represent the collection of combinations. At the start, they're empty, meaning that
5:02:05
I have no combinations for most of these elements, except for one, right, we already spoke about table at index zero, right? That should be a 2d, empty array. And the reason was, still, the outer array here represents the collection of combinations. For the empty string, there is one combination that you can use to make it right, that is the empty combination, where you take no words to the word bank. Cool. So now I can begin my general algorithm by
5:02:31
just iterating through my target, and you've done this many times before. So I'm iterating through my table. And what I'll also do is look at all of the words, right, so in every iteration, I'm going to consider some words of the word bank. So I'll say that word of word bank. And like before I send you to check that, alright, these words better have matching characters based on my current position. So I'll use that classic logic, right, seen it
5:02:55
many times by now. And I'll slice a segment out of my target string, I'll say target dot slice starting index i, and grabbing the next word, dot length, number of characters. Cool. I'm going to compare that chunk to the current word that I'm iterating through. Nice. So using this statement, I'm sort of filtering down all the words, and only going to do some logic on the words that match based on my current position. Nice. And so we've seen
5:03:24
you know, this nested for loop an if statement before, right, we're now we're adding our new logic within this if statement. Cool, all I need to do is really understand what types of data I'm dealing with here. All right, so let's say I just wrote this expression table at index i, well, that's going to do is just reference my current spot in the table. And if I think about what data it's going to be, it's definitely gonna be an array,
5:03:47
right? It's either going to be like an empty array, meaning there are no ways to make this current target. Or it could be a multi dimensional array, where every sub array represents one way I can make the current target. So if this is all of the combinations that generate my current, then what I'll do is I'm going to map over them. Remember, in our drawing, what we did was kind of copy over all of our current combinations. But then make sure we also add
5:04:13
our word that we're using right now to the end of each of those combinations. So that's what I'm doing right here, and a map over every summary. And what I'll do is, I'll just copy over the elements of that summary using that spread syntax that we've seen before. And then also be sure to add on at the end my word. Nice. And then that will give me let's say, our new combinations. So I'll just say that to a variable maybe. So new combinations
5:04:42
is going to be a 2d array, right where every sub array represents some combination. And I want to take these combinations and add them into that further spots inside of my table. So I know I need to kind of look at in my table. So I can look at table at index i plus word dot length. I know that all positions of the table are going to be arrays, right? So this is going to be an array, there's going to be some data that might already
5:05:06
exist at this position, right? So what I don't want to do is just assign you combinations, because then that would overwrite any previous existing combinations that I already found for this position. Instead, I need to make sure that I just add these new combinations to that list, right. So what I'll do here is I'll push to that array, I'll push all of the elements of my new combinations right here, I can spread this out, I want to spread
5:05:32
it out. That way, I don't add any additional nesting over here, right. So this is looking pretty good. I think let's go ahead and return the table at Target dot length. Here, I have some examples down below. Let's give this a shot. Nice. And these answers look correct. Right, notice that these last two examples should return empty arrays because they are impossible to generate. Cool, let's hover over this code for a moment. Probably the
5:06:03
most tedious logic here would be these two lines, right? Really try to understand how like these two lines translate into the logic we did in our drawing. So let's break down these lines again, right? line 11 is going to take all of the combinations in my current position in my drawing that was like my yellow box. And it's going to add our current word to each of those combinations. And then we're going to take each of those new arrays and
5:06:31
add them to the list add our further position, right being sure not to overwrite, we already spoke about the complexity of this one, it's definitely going to be exponential, probably a little more than exponential. Right? If you imagine all the work we have to do using these maps and like spreading, we have to actually construct our result array, which is going to contain an exponential number of things. Right? So when I look at this last
5:06:57
example, let's say that I made it a little longer, right? So let's say actually pull up the size of that input. It's going to be very, very slow might even crash, but let's just do it. So let's say I had a bunch of A's here, just for fun. So if we try this example. Yeah, it looks like our program still crashes, right? This is going to return a really, really a massive array probably can't even fit into memory over here, right? So
5:07:27
we'll get like a stack size exceeded, even though this isn't even recursive, right? Just calling functions way too much over here. So no matter what we do, we really expect this problem to sort of demand an exponential solution. With that, let's head back into the drawing board where you can wrap up this course. Alright, programmers, by now we solve many different dynamic programming problems together. And I want to leave us with some final advice. So whenever you're starting to attack any
5:07:52
dynamic programming problem, start by really taking a moment and noticing any overlapping subproblems. And then from there really focus on like the input to the problem, in particular its type. And from there, you shouldn't be able to recognize what is the trivial smallest input? So in our string problems, usually that means the empty string in our array problems, it's the empty array, or in our number problems, it's usually a number like zero or one, right?
5:08:17
Is there some input wherever you don't really have to do any extra work to know the answer? The answer just sort of is what it is. Once you recognize this trivial scenario, or the base case, really, then you'll want to realize how you can relate this base case toward your larger inputs. And then you have two options, right? You can either think recursively, and use memorization, or you can think more iteratively and build a table using our tabulation formula.
5:08:42
I think as you practice dynamic programming problems, I would actually always solve problems in two ways, one using memoization and one using tabulation. And of course, from that point on, it's okay, if you have like a favorite strategy. For me, personally, that's memorization. But that being said, it really helps to have options when you're in an interview. And once you've made that decision on, you know which route you're going to take, definitely, you
5:09:04
know, slow it down and draw a strategy first. This is I think, the most important thing about just data structures and algorithms in general. Usually, when we draw our pseudocode, or draw our process on the whiteboard, we can recognize all of these edge scenarios. And it's much harder to do when we just write like the code out of the gate. And so I promise if you slow it down and take a moment to draw a visual, you're gonna find your work a lot
5:09:29
more productive, as well as more intuitive when you explain it to someone else. And of course, through all of that, you're gonna have a lot more fun, you know, dealing with these quite hard topics. Alright, programmers, that's all I got for this course. Hopefully, you had fun, you know, learning this new topic. I definitely had fun teaching it to all of you. So what you want to do now is head down to the links in description and head to coder
5:09:49
byte comm where you can actually practice this new topic. Thanks for watching, and I'll see you in the next one.
Here to help you learn
Sign in to keep a private conversation with your course tutor.
Ask me anything about the material…
Sign in to chat