Transcripts
1. Introduction: Hello everyone and welcome to this new course which is about dynamic programming. My name is 100 units and I'm going to be your instructor throughout this course. So first of all, let me start by showing you the schema with the outline of this course. We're going to start by defining dynamic programming. And we're going to learn about two of the most popular techniques that are usually used within this topic. The first one is memorization, and the second is tabulation. And we're going to learn about them using the Fibonacci sequence. We're going to solve this problem using three methods. The first one is using the generative recursion that we all know. And we're going to move on to memorization and tabulation. And we're going to see the differences between them. And we're going to learn when and where to use each one of them. After that, what we're going to do is to solve some of the most famous exercises using dynamic programming. So the first thing we're gonna do is to try to build a tree or maybe sort of an array or a 2D matrix of this problem. After that, we're going to try to write a pseudocode that will help us to implement this problem. And finally, we're going to actually implemented using three languages, Java, JavaScript and Python. So going through the sections, you may notice that we're going to solve one main problem in each section. And the problem contains the explanation of the problem alongside the code or example work through. Then we're going to have a pseudocode that explains our logic and formulas. And after that we're going to implement it using the three languages mentioned before. We also have one additional feature that is this website. I created this website in order for you to run your code and tested. So here we have some problems that we're going to solve. And you can go ahead and choose one of the problems. Try to solve it here before going back to the video explanation and implementation that we have and discourse. So that said basically, this is the schema or the outline of our course. I hope you enjoy it and see you in the next section.
2. Requirements : Okay, so before we start, there's a list of requirements that you need to download according to the language that you're going to use. So for example, if you're using Java, but you need to download is Eclipse or some sort of IDE where you can run Java. Then of course you gonna need to download Java. You're going to head over to Java SDK and they just kinda press and agree and such free download. And you'll get your newest version. If you're using Python, for example, you need to download Python. And of course, I'm going to download Visual Studio Code where we're going to run our code with Python and JavaScript. Finally, for JavaScript, we're going to use Node.JS to run it on our server. So these are the requirements that you need. I'm going to add the links in the description section. And I hope you enjoyed this class. So see you in the next section.
3. Fibonacci Sequence: All right, So hello and welcome. And these couple of videos, we're going to answer the question of what is dynamic programming? So let's start with something simple. That is the Fibonacci sequence. And the Fibonacci sequence is actually a sequence where each number is the summation of its two previous numbers. So our base cases are actually the first two numbers, that is 01. So these are the very first two numbers in the Fibonacci sequence. And the rest of them are actually the summation of the previous numbers. For example, if one I get this number, it is 0 plus one is one. Then we have 1 plus 1, 2, 1, 2, 3, 2 plus 35, so on and so forth. So this is the Fibonacci sequence. Now whenever we want to solve it, our first thought goes into recursion. Since each time we want to compute the number at a specific position, we need to go back to the previous numbers. So let me just write the indices right here. So this is index 0, 1, 2, 3, 4, 5, 6, and 7. Now let me just draw a tree where we're going to represent these numbers. So let's suppose I want to compute the Fibonacci of five. So to compute the Fibonacci of five, I need to compute the Fibonacci of four and then the Fibonacci of three and then sum them together. Now in order to get this Fibonacci of four, what I should actually do is to compute the Fibonacci of three and then the Fibonacci of two. And the same thing applies here. So I want to get f of 2 and f of 1. And here we'll meet to get f of 1 and f of 0. And remember that f of 1 and f of z are the base cases. And whenever we get to this point, we should actually just return these two values that we have right here. So here we have f of 1 also and f of 0. And the same thing applies here. So I'm just going to write these dots. So that's it basically now, if we think about the time complexity of this algorithm, it will take an exponential form, since as we can see, we are computing the same numbers over and over again. So here we have f of 2, 2, and here we have f of 1, 1, and 1. And you are actually computing them over and over again as we can see. So our solution might work, or it actually works for small numbers, but it will take a long time, might take seconds, minutes, or even hours to compute a large Fibonacci sequence. So what absolute code might look like? So let me just write the Fibonacci and it should be equal to this code. So the first thing we're gonna do is to write our base cases. If n is equal to 0. So if n is at index 0, we should just return this value which is 0. So I'm just going to simply return 0 in this case. Now if n is equal to 1, what we should return as actually this value at a specific index one, which is actually one. So I'm going to simply return one. Now we can start with our base case or I'm sorry, with our recursion. What we need to return actually is the two previous numbers. So if we are to Banaji of n, which is equal to five, we should pretend to Fibonacci of four plus Fibonacci of three. So how did we do that? We simply called the Fibonacci function of n-minus-1. And then we sum it with the Fibonacci of n minus 2. So that's it. Basically this is for our pseudocode. Now what I'm going to do is to take the spirit of God and actually implemented using Java. Keep in mind that we are only going to use Java for the purpose of visualizing the time complexity in this problem and the rest of your problems will be presented in all languages, Java, JavaScript, and Python. So to do that, let me just head over to Eclipse. And what I'm going to do is to write this code here. So f n is equal to 0. I'm going to do is to simply return 0. Now if n is equal to one, I'm going to return one. And if these are not the cases, what I'm going to do is to simply return. So I'm going to return Fibonacci of n minus 1 plus Fibonacci of n minus two. Now, after that, I'm going, I'm sorry, I forgot here. Now to test this, what I'm going to do is to create a main function and call the Fibonacci of a specific number printed out, print out the Fibonacci of 7 in this case. As you can see, if I go ahead and run this code right here. But I'm actually going to get as P number 13. And if you go back here, we can see that this Fibonacci of this specific and X7 is actually 13. So our code works correctly. However, if I go back now and let's try the Fibonacci 50. And if we run this code Tuesday, some time to be executed since we have recursive calls where we're going to run the same code or execute the same function over and over again. And it will take maybe seconds or maybe minutes in this case. So we need to have a better way to just get these Fibonacci sequences or the results in this case. And here comes in dynamic programming. So we have two techniques that we're going to present with. The first one is called memoization, and the second is called tabulation. And we're going to present them in the next couple of videos. So see you then.
4. Memoization : All right, So we found the solution where we use recursion to solve this Fibonacci problem. However, we run into a problem because of its time complexity. Because we are running the same function or calling the same function over and over again. So how do we deal with that? Here comes dynamic programming. So the first technique we're going to use is called memoization, which is basically just to store the values that we're going to use over and over again. So in order to do that, instead of just calling f of 2 here one time and here another time. But we actually go to two to solve this f of two the first time we see it. So our code is going to work this way. We're going to call f of 5, 10. In this case, it will call it f of 4, 4, 3. However, before calling this, it will go this way. So the flow of our code is actually being f of 5, 4, 3, and then we're going to go all the way till 21, and we're good and then we're gonna go all the way back here. And as you can see right there. So this is the flow of our code. Now what we've done to basically do is to store all of these values every time or the first time we're going to see them. And of course, whenever we want to use them again, we're just going to take them from our memory. So to do that, what I'm going to actually add in this case is a list here. So let me just delete this. And I'm going to change the parameters right here, from N into N and a memory. And in this case, what we're actually going to do is to take this memory and use it later. So before doing all of these, we're going to check if the fibonacci of this sequence, and it's actually stored inside our memory. So how do we do that? Let me just change the color in order for us to visualize the changes. So if the memory at this specific position and is not equal to 0. Now remember that whenever we create this memory, we're going to just put zeros and Annette and FDA's position, which is at n, is not equal to 0. What we're actually going to do is to simply return it as it is. So we're going to return the memory at this specific position. And now if this is not the case, we're going to continue with our code as before. However, before returning this one right here, what we're actually going to do is to store it inside our memory. Because remember that Fibonacci n is returned by this right hip. So to do that, I'm simply going to store it at memory at n and then returned. So let me do that by simply just taking all of these and just maybe push them to hear. And what I'm going to do now is to take this and place it here. Now, let's continue. So instead of returning this one, and I'm going to do is to just put them inside our memory and return the actual memory. So let me just try it here. We have memory at n will be equal to this one. And of course, after that, we'll simply going to return the memory at this specific position. And so that's it now, instead of calling all of these functions over and over again, who just going to check if they are at this memory? If this is the case, we'll simply going to return them. If this is not the case, we're going to compute them and store them inside the memory for the second time, we're going to use them. Of course, it will work properly. Now, let's go ahead and use this pseudocode and our Java. So instead of just getting n, I'm going to take a memory. And of course when we call to the Nazi here, we should also return memory. However, before returning it, what we should actually do is to just add a tail. So memory at n should be equal to ds, and of course we should fit on memory. And after that, Now, let's call it criteria. So as you can see, this large number took awhile to get and it is negative because we were using integers. So maybe we're going to use 24 now. However, we need to increment it. So we're going to have a new end of size 21 to use inside pseudocode. Now if we go back and run this code, as you can see, we got our result which is 67, 65, which is, we didn't take much time as before. So now let me check for the number 30. And as we can see, for undiscovered, we're going to get this large number and this number who could have not just computed using the original recursive function because we're calling the same exact functions over and over again. So now what we're going to do is to try for a very large numbers such as 20000. In this case, if we go ahead and run it, we can see that we got an error. And this error is actually StackOverflow. So our code will execute fastly. However, whenever we call these functions over and over again. So if we are at a specific position where we have 10 thousand, we are going to call ten thousand, nine hundred thousand, nine hundred ninety nine thousand, nine hundred and ninety eight all the way until the last one which is at 0. So all of these a call back functions or callback SysML are going to be or the or just stored in a stack. And our staff might not take all of these or fit all of these together. So what we're going to do is to use another technique that is called tabulation. And it is also a dynamic programming technique, and we're gonna see it in the next video.
5. Tabulation : Okay, So in the last video, we use memoization to solve this Fibonacci problem. However, we run into a problem where we had a stack overflow error because we were using too many return statements, callbacks, and we're storing all of them inside our stack and it couldn't fit them. So now, what we're going to do is to use tabulation to solve this Fibonacci problem. Now, if we know that we need to get this f of five, and in order to get this f of 5, we need to get f of four, f of 2 and f of one. So it makes sense to solve all of these beforehand and just store them in a sort of array list or something like that. And then just return f of 5. So what we're going to do is to start from the bottom till the last element. And this is called tabulation, which is basically bottom-up dynamic programming. And actually called this because we're going to build it from the bottom, one by 12, preaching our purpose. So what we're going to actually do is to start from 0, fill our function, or through our rest, and then return the last one that we need. So let me just delete all of this pseudocode and write it again with tabulation. So I'm going to actually do is to create a function and it will be a iterative function, so iterated. And in this case what we're going to do is to have a number and that we're going to return. And in this case, what I'm going to do is to create maybe a list or an array. I'll simply call it a list. And it will be of size and plus one. And what we're going to do actually is to fill this list with these values right here. So the list at the specific index 0 should be equal to 0. And then the list at a specific index 1 is equal to one. And then we can start with a for loop starting at I equal to two all the way till n. And each time inside this list we're going to store that specific index I, the value of the list at i minus1, and the plus at I minus two. So it will take a big O of n. So this is the runtime complexity because we're looping through all of the elements from 0 to n. And whenever we reach the last element which is at a specific index, and we can return it. So after finishing from all of these, we simply return the list at the position. And in this case, so that's it basically now, instead of calling back each and every time we need to call this, for example, f at 99, 99, we can simply store it in our list and finally, get it whenever we wanted. So in this case, let me just read type this function right here using tabulation. So instead of getting all of these, what I'm going to do is to simply create a function and it will be. And instead of storing that parameter, I'm going to simply write it right here. So I'm going to have the ma'am right here of size n plus one. And in this case, what I'm going to do is to store at Mammoth 0 the value of 0, the mom of one will be one. And now we can start with the for loop, starting from I equal to two all the way. And so included. And of course we're going to increment it after that. What I'm going to do is to start at this specific position at i, the value of m at I minus 1, and add to it the value of n minus two in this case. As we can see, if we go ahead and return the value of and at the end, what we are going to get actually as the correct value of this 20000 right here. So if I run this code, I'm going to get 93637285. And this is the correct Fibonacci sequence at a specific index of 20000. So we just get rid of the StackOverflow problems that we used to have using memoization and we already used tabulation in this solution. So that said basically for the memorization and tabulate, what we're going to do next is actually to solve some of the most famous dynamic programming problems using memoization and tabulation. So what we're going to do is to see the problem, read through it, and work through an example of a tried to solve it using a hand. And after that, we're going to create or just generate a pseudo code. And this will help us to implement it in our languages, Java, JavaScript, and Python. So the schema of our costs will be as follows. We're going to have the problem than the pseudocode and then the implementation. So that's it, basically what this video see you in the next one.
6. Minimum Number Of Bills to Return an Amount: Alright, so in this video we're going to go through one of the most popular examples that is usually solved with dynamic programming. And the problem goes as this. So imagine you have a store and a customer comes in and ordered with $60 worth of food. Now he hands you a $100 bill and in this case you're going to return the leftover, that is the $40. So for example, let's suppose we have a $100 and he buys with $60 and should return him for. Now, for the sake of this problem, let's assume that we have four types of bells. So let's suppose we have the $1 bill. I write them right here. So we have the smell and is the $1, we have the five-dollar. We also have 10, and we also have the 25. So that's it. So we have these four types of bells. Now, if we want to solve this problem using a greedy algorithm, let's try it right here. For this example, we have a $40 return. And in this case, the greedy algorithm goes as this. The first thing we're going to do is to search for the largest bill possible that we can pay with. So in this case, we should return $40. So let me write it right here. So this is the $40 that we should return. Now we're going to check alongside these four types, what is the largest amount that we can extract from this 40? In this case, we have the 25, so $40 minus 25. So we use this 11 time. Now we're going to have 15. And in this case, we also have a 10 that is smaller than 15, so 15, we can extract them. So we use this 10 also one time. And this will leave us with five and then escapes. Finally, we have five minus five, which is equal to 0. To solve, we also used this 5 one time. So we ended up with 25 plus 10 plus 5. And this case, this greedy algorithm actually works and it gives us the most optimal solution, which is using 25, 10, and $5 bills. Now, imagine we also have a 20 dollar bill instead of just having these four types. So let me just delete all this and let's try it again. So if I have right here another 20 dollar bills, and let's try the greedy algorithm one more time. In this case, now we already have defaulted dollars that we should return. And in this case, the greedy algorithm will work exactly as before. So we're going to search for the most or the largest belt that we can extract from this $40 should be less than this $40. However, we have 25. So we're good. We're gonna be left with 15. And in this case, if we want to work with a $20, we can't because now we have 15. We need to search for anything that is equal or less than 15. And this case. And so we're going to be left with the same exact thing as before. And this is clearly not the optimal solution. So the optimum solution is to just simply use the 20 dollar bills times two. So we're going to use this 20 dollar bills two times and we're going to get the $40 that we need to get to return to the customer. And in this case, as you can see, the greedy algorithm won't work. It will actually be not the optimal solution. So we're going to use dynamic programming instead. So let me clear all of this out and we're going to go through another example using the dynamic programming method. Right? So this is another example. So we have $7 that we should return and we have the 1, 3, and 4 belts. In this case. These bells constitute the ones that we draw before. So don't worry about it, adjusts with them and enlist. And in this case, what we're going to do is to construct an array or a list. And we're going to talk about it in a second. But first of all, let me just constructed and this array will be upsized, this seven plus one. So in this case, I'm going to just draw seven. All right here, so 3, 4, 5, 6, 7. And as we said, some plus one, which is it an S case, the indices will be 0, 1, 2, 3, 4, 5, 6, and 7. So as we said, we have eight elements in this list. And what we're going to do is we're going to go through this list of bells one by one and check for possible implementation of possible addition in this right hip. So in other words, what we're going to do is to check, for example, if we only have a $1 bill, what's going to happen for these right here? So in this case, let's try it out with the $1 bill. So for example, if we have this $1, but how many bills do we need to constitute the 0? And in this case we don't need any built, so we just write 0. So this is just a base case. Now, let's suppose we need to return $1. How many $1 bills do we need to return $1? We just need one. Now, let's move on to the second. So for example, if we have, we need to return $2. How many $1 bill doing it to return these $2 would just need to $1 bills. So in this case, what we're saying that we need to $1 bills to return the amount that is $2. So to make it a bit easier, these are the amount and these are simply the minimum number of bills that we should return in this case. So what we're saying here is that we only have this $1 bill, and this is the minimum number of $1 bills that we should return if we want to have these amounts. And well, without going through all of these, it's the same. It's pretty straightforward. So we need $3 bills to return an amount of three. We need 4567. So that's it. Basically this is what we need. Let me just delete this and let's continue with it. So in this case, we have just gone through the $1 right here. So what we need to do right now is to check for the $3. Now let's suppose we just, we don't just have the one diabetes. We have the $1 as well as the $3. But in this case, what we're going to do is to check from the beginning. So at 0, how many dollar bills would do we need to represent the 0 amount? We don't need any. Now, three, how many $3 bills do we need to represent one we can to prevent one with $3 bills. So we move on to two. In this case, we're going to check also and we came to present two with $3 bills. So we're going to move on to this three right here. And in this case we ask ourselves, how many $3 bills do we need to represent this $3 amount? And the answer is pretty straightforward. We don't need three, we just need one. Now, what we're saying here is that we need one Three Dollar Bill to represent this amount. And let's move on to the fourth one. So how many bits do we need to represent this four? And actually we just need to bills, that is the $3 bill plus the $1 bill to present this for. So we don't need for belts, we just need to and this case, it is three plus one. So what do we do? We cancel this and replace right here too. And as for the five-dollar, how many bits do we need to present the amount of 5? And actually we need three bits. That is the $3 bill Plus one Plus $1 bill then is 3-year right here. Now as for the sex, and how many bits do we need to present the sex? We actually need, just to remember that three, we have as many as we want. So instead of representing it with six ones, we can present it, it represented with two threes. In this case, we just need to now move on to the seventh. And in this case, what we're going to do is to use $3.3 births, I'm sorry. And that is $2 to $3 bills and 1 $1 bill. And in this case we're going to end up with something like that. We have 01212323. Now, let's move on to the final one. That is to represent the fourth one. So now we also have the $4 Belt. In this case, we have the 1, 3, and 4 dollar numbers all at once and we can use all of them in this case. Now what we're going to do is to skip all of these until the four because we can't represent any of the smaller amount, 0, 1, 2, and 3. And we're going to go all the way to the fourth. And in this case we're going to ask ourselves as before, how many $4 bills do we need to represent default dollar amount? And the answer is one. Then how many? For dollar bills or any bells, we need to present the five and the answer is quite straightforward. That is, we need $4 bill plus $1 bill. And in this case, there are two. And the same thing goes for this. So here we have two. And of course we're going to check. So now we have also four. So four plus one plus one is equal to $6. So in this case we used three belts, and this is not optimal. We already have a solution that works better with two belts. That is the 2 $3 bills. If we have three or two, we're going to choose to stay with this two. And finally, if we're going to ask ourselves for the last one, that is the $7. In this case, we're going to need 4 $3. So can represent it with three instead to a set of three. So that's it. Basically this is how we got with a finite answer. That is, we can represent this amount using just two bells. So that's it for the idea of the work through now. Small pseudocode to see exactly what's happening and how we can think about it that way. So what did we say when we were at three or four? We said that we can skip all of these, 43 since they are smaller than three. And let's denote this actually by the bells right here. So these are the beliefs that we have. These are the minimum number and this is the amount. Now in this case, if the bell, so the bells are 1, 3, and 4, so bell stands for either 12 or three. And in this case, if this bill is less than or equal at the amount that we, that we are looking for. What we're going to do is to update the minimum number. And if we go back to our example, we can see that the minimum number should be one of two things. That is either this one right here or we need to update it as here. So for example, 012, we didn't need to update them. So they sent the same or the updated ones, that is 1, 2, 2, and 2, as we can see above. And in this case, how did we get these updated numbers? So if we look to the four this case and this four bills, what we actually did is that we took this four from each of the amounts that we. So let's think about it for a second. So for example, in this case, when we had this five right here, so we have $5 to return. And this case what we did is that we subtract $4 from here. So we have 5 minus 4, so we still have $1. And this case, what we're going to do is to look at the $1 amount right here in the table. This is the $1 amount. And in this case, what we did is just that we took this minimum number right here and added to the how many bills, how many $4 bills did we use? Here? We just used one bill. That is the $4 and we still need to return the leftover amount that is $1. In this case, the data set right here. We have the one right here. So this is the amount that we should return. So 1, 4 dollar bills plus 1 $1 bill. And this case, the answer is two, as we can see, that is using this formula. So what we're going to do after that is that we're going to write pseudocode for this actually. And then we're going to implement it in Java.
7. Pseudo-Code of the problem: All right, so now that we actually know how this algorithm works, and we went through an actual example. We already know the idea behind of it. Now, let's try to come up with a pseudocode that will help us and our code writing in a bit. So if we wanna go through the pseudocode, as we said, hefty bill is less than the amount. In this case, what we're going to do is that we're going to update this minimum number right here. So what we're going to do is to pass through all of this list for each one of these belts. So we're gonna have two for loops nested in each other. The first one is will be, will be the bills bills loop, and the second one will be the minimum number that we're going to update each and every time we pass through number. And in this case, what we're going to do is to update the minimum number each time the bill is less than or equal to the amount. In this case, for example, we had for exam 4, 3 bill. We already have this 012 and there are smaller than three, so we don't need to update them. We start with the amount that is bigger or equal, this belt right here. So as we said, we start from here all the way that the end for each and every one of the belts right here. So what we're going to do is to check the minimum between two things. As we said, the minimum between this number right here and the actual number that we can update. So what we need to do is to change the minimum number. Minimum number at this specific amount should be updated. In this case, it will be equal to 2, one of the things that is the minimum between them. So it will be equal to men between the first thing and the other. And as we said, the first thing is the actual amount that we already have. So it will be the minimum number of the amount. So it's the same as before, or we need to have a smaller one. So what we're actually doing is to simply checking if our new solution is better than the other one. So as we said here, we already have these solution 01234567, and they are represented with this $1 bill. However, for the amount of three, for example, we can represent it with the amount of 3, 0, the one Three Dollar Bill. In this case, we remove these three bells and we just added one belted is $3. And in this case, it's much better and more efficient to use 13 dollar bill instead of 3 $1 bills. So what we did actually right here is that we took this amount three and just, just attacked the S3 bill from here. So we left over with 0. And this case we went all the way back the amount of 0 and we look at this minimum number and in this case 0. And so what we actually did is that we only used one pill right here. And then we check for this 0 amount. And we actually used a 0 bell right here. And this will leave us with one bell antigen. So this is why we have three right here. And the same thing goes for this six right here. What we actually did is that we used 2 $3 bills. So we this x right here, minus two times three, which is equal to 0. So this three is used twice. So use tuples. And we went all the way back to the minimum number or the amount of 0 and we checked it's minimum number, that is actually 0. So we, we use 02 minus 0 to plus 0, I'm sorry, is equal to two. So we ended up having to bell strike him. So this is the actual work through. So if you want to think about it in another way, for this six belts right here, what we actually did is that we said it's either 6 $1 bills or something else using these three, Dahlberg right here. And in this case, what we actually did is that we just took this $3 bill. So it's six minus three. And this case, we ended up with three, right? So this, we only used one bill from here. And then we checked at the amount of three, which is right here. How many, what is the minimum number in this case that we need to end up with a returning all of the amounts that we have in this case for three, we can clearly see that is one. And this is how we got one bell plus 1, which is equal to two bills. So this is it. This is a general idea. If we have multiplication in this case, we can use this directly. However, this is the actual way. So let me, let me just delete these and We're good. We can continue. So here we Mr. well, I'm sorry. So here we have Bill. So if the bill is less than mount, as we said earlier, we need to update the minimum number, which will be equal to either the same or the, we add one, as we said. So it's one bill plus the minimum number at the amount minus the bill. That makes sense. So let me write it and then I'll explain it. So minimum between the actual amount that we have minus the belt that we pad that we have. So that's it basically. Now if we want to go through this example using this formula, Let's go ahead and do it. And of course, I'm not gonna go through all the example. I'm just going to take specific situations. So for example, let's suppose we are at this five right here. And we just have the 3 $1 bills that we can represent this 51 and this case what we're going to do. So we are at this stage right here. And we're going to think through the process. We have this $3 bills. And in this case, what we're going to do is that we're gonna add one. So it's either the minimum between two things, right? So it's either this one right here, which is five. You don't see it right now because we just remove it before, but it's right here. And this is five. So it's either five or something else. And using this formula is one plus the minimum amount, minimum between amount, mind, spirit. And in this case, what we're going to do is, so it's either five or one, plus. We're going to go all the way to minimum number of amount. In this case, the amount is five. The builder cupid is three. So the minimum number add 5 minus 3, which is minimum number at two. In this case, we're going to look at this. And as we can see, we have the minimum number in this case is two. So 1 plus 2, which is 3. So the minimum between 53 is actually three. And this is what we have right here, is the number three. So we can represent the $5 bills with one Three Dollar Bill and to $1 bills. So that's it. This is how we can use this formula. And if went try it for the last time, we can try it for this one right here. So before this, we had a three here. And in this case what we're actually doing is that we're going to add one for dollar bill. So let me just delete this and let's continue. So the minimum between two things, the actual amount that we have or the actual minimum number that we already have, or we need to update it by adding one for dollar bill. So he has one. Plus. We go to the minimum number at the amount which is 7 minus wL, which is 4. So 7 minus 4 is 3. So we're going to go all the way to this three right here. We're going to look at the minimum number. In this case, it's one. We're going to add one right here, so it's the minimum between 32. So the answer is two. That's it. Basically this is how we can use this pseudocode to help us write our code right now, this is the hardest part. We just come up with this actual method or actual algorithm or idea that we can use to solve the specific problem. And using this method, we were able to come up with the most optimal solution. Unlike the greedy algorithm that we had at first. In this case, as we said, we can represent this $7 built with one for dollar bills and 13 gullible. And this case, the answer is two. And with that being said, this is the end of the pseudo code right here. And the next video we're going to implement our function using Java. So see you then.
8. Minimum Number Java Implementation: Alright, so now that we know how this algorithm works exactly, and we wrote the pseudocode that is going to help us in our code walk-through. Right now. We can start with coding. And actually this is one of the most important, but you should always start with this, something like this. So you can write your code or write your thoughts on a piece of paper and maybe draw some things. In this case, we draw this list and we updated every time we pass through a bell. So you'd been a need to work with a pen and paper and not just visualize all of the things inside your head. Especially in dynamic programming. Because visualizing something or you had works usually foil simpler problems. However, in some deep or complex problems, you always need to use a pen and paper. And this case, let's go to our Eclipse. And in this case what we're going to do is to start with creating the function. So I'll simply, we just need to Min returns the minimum number of change, which is an integer and an empty function minimum number, in this case, what we're going to take it, the amount that will return and it is denoted by N. And how many or the type of belts that we have. In this case, we're going to name them bells. So let's open it up and we're going to start with implemented that. So the first thing that we're going to do is to create this list that we talked about earlier, and this is the minimum number. So to create it, I'll simply create a minimum number list. And it's actually contradicts the, it's the same as the method, right? Four, so intimate differently. And in this case, this will be size, the number or the amount of plus one, as we said. And what we're going to do is at first to fill it with the maximum value that we can. So we're going to use arrays that felt. And what we're going to do is to fill this bells with integer, that max value. This is how we can store the max of integer value right here. And it seems that we need to import arrays. So we just try contrast space, hit Enter, and it will just take it right here. Now, this area, good that we didn't return the integer yet, but we can handle it later. But for now, what we're going to do is to remember that we always want to start with amount of 0. So the minimum number should be 0. In this case, what we're going to do is to store and the, I'm sorry, it's not doubles is the minimum number right here. And we're going to start at minimum number at 0, we're going to store 0. So this is the first step. Now we're going to pass through all of the actual data. So what we're going to do is to pass through the bus and inside each, well, we're going to pass through the amount in this case. So int I equal to 0 all the way to the bells, that length and then updated. Now, the second one will be j equal to 0. Then J is less than the minimum number. I'm sorry. So here I added S by mistake. And now we're good. So we're going to go all the way to the minimum number that length and then updated. Now, what we're going to do is to check if the bell is less than the amount. So how do you do that? We simply check if the bells at I is less than something, which is the amount. And in this case, the amount is actually the index. As we can see, the amount is the index of this minimum number array or less. So it's, if it's less than or equal to this amount, we're going to do something f naught. We're gonna, we're not gonna do anything. In this case. What we're going to do is to take the difference between this amount and the bell. So we can say that this j is the amount and bills at ISB actual bell. So the difference will be j minus belt satire. And we also want to compute the bell in this case. So I'm going to denoted by maybe it might be the minimum number in this case, again, I just denoted by B. And what we're going to do is to add this one plus the amount or the minimum number. This difference. So what we did actually here is that we computed the formula. The formula says that it's the minimum number. And the minimum. This is the updated new one. It will be one plus this right here. And how we computed this is we actually took the minimum number and amount minus bell and it strikes him. So 1 plus 1 plus the minimum number. So this is how, this is the minimum number at amount minus the bill. And we compute the difference just in the earlier line. In this case, we got the one that might be updated. So in this case what we're going to do is to return. Just said that belts at I will be the math, but men. So it's one of two things. It's the I'm sorry, the minimum number at I and j. I'm sorry. And it will be one of two things. It will be either the same as before and, or the BI that we just created earlier. And this case, we can update these minimum number easily. So what we did actually is that we took the difference between the amount and the bill, we computed that the minimum number, we just compute this formula and we got this right here. Then we said that minimum number at this amount should be equal to the minimum number at this around or one plus the minimum number of amount 2012. And this case, we got it right here, we updated it. So it's either the same or the one that is TBI. Now, what we're going to do is to check if the minimum number at the end or at yes. So at the amount is not equal to Emax value. And you're going to tell you why in a second. We're going to return minimum number at and else return minus one. So what we actually did here is that we checked, we can actually do or return this amount. In this case, if we can get that last value shouldn't be the max value. It should be a natural number. And if this is the case, we just return this number. And if not, we're going to return minus1, same that we can't compute or we can't have this return with this, this bill strategy. And one example of this is imagine that we need to return a $5 bills or $5 amount and we just have 78 doubles. In this case, we can't return five because we just have 78. So this is why this will always be max value and we can't return the amount, so we just return minus one. So that's the implementation. I think it's pretty straightforward after all of the explanation that we did right here and walk through. And that's it for this video. See you in the next one.
9. Minimum Number JavaScript Implementation: Okay, So in this video we're going to implement our function or the pseudocode that we created earlier using JavaScript. So without further ado, let's just get right into it. The first thing that I'm going to do is to create the function name at minimum change. And in this case it will take and bills as parameters. Let's open it up. And in this case, what we're going to do is to create an array in JavaScript. We can do that. Let's name it. Let's name it. Actually the amount. And what we don't want to do is to take this amount. And of course we're going to go through all of these in a bit. But for now, what we're going to do is to create it as an array of an plus 1. And we're going to fill it with infinity. So that's it, basically this, how we can create an array in JavaScript. Now what we're going to do is to update this amount into the first one should be equal to 0. So if we go back to this one, we can see that this amount should be equal to 0. Actually, let's name it minimum numbers, since we made that here, minimum number. So we're going to just, I'd hear minimum number. Same thing applies here. Now what we're going to do is to create our for loop. So the first thing that we're going to create is the for loop for the bells. So what we're going to do is to create, build and bells, bells, and then open it up. Now, the second one will be for the actual minimum number. And we're going to denote these indices by amount, as we said right here. So we're going to create it here for the lab. Amount equal to 0, then the amount should be less than the number, minimum number that length. And then of course, we're going to increment the amount. Now let's open it up and now we can start with our actual code. We're going to simply write the pseudocode that we wrote earlier. So it's says that if the amount is greater than or equal to the bill, we need to do something. In this case, what we're going to do is to update the minimum number, which will be equal, should be at amount to be equal to the minimum between two things. So we're going to use method men. And this minimum will be the number of minimum number of amount and the minimum number of amount minus the bill. Now what we're going to do, of course here we need to add one. So it's the minimum number of amount minus p plus 1. And in this case, we're done actually with this function. This is how we can implement it using JavaScript with this pseudocode that we created earlier, with just using the mattered meant to take the minimum between these two things. And of course we'll fill in it with infinity. And don't forget to fill the first one with 0, since it is such as the base case right here. Now what we're going to do is to simply return these right here. So keep in mind that if this function works properly, it should update the last one. However, sometimes we may have the infinity at the end. And in this case, if you have infinity, this means that we didn't solve the problem, there is no proper solution. So let me give you an example for such thing that suppose we have the five-dollar to represent and we have 678 as well. In this case, there is no proper solution and this last infinity will not be updated since $5 cannot be represented with 67 or either $8 bills. So what we're going to do is to check if this last one is equal to infinity, we're going to return minus1. Otherwise, we're going to return the actual minimum number that we got. So now, if we actually return this, let me just return it right here so that return minimum number at, and what we've done to get a simply the last one in the list. So this is the list that we're going to get 0, 1, 2, 1, 1, 2, 2, 2. And we're going to get the minimum number. Now, to make it more clear, I'm going to return the whole list at first and then we're going to discuss it. So the variable n will be equal to actually the actual data right here, which is seven. And the last would be 1, 3, 4, so and equal to seven. And the list will be equal to list 134. And in this case, what we're going to do is to call this minimum change function with an and bills. And of course we're going to login. So console.log and luck this function. Now if we go back here. And let's go to JavaScript, dynamic programming. And what we're going to do is to simply use node men, change that JS and we're going to get 0, 1, 2, 1, 1, 2, 2, 2, which is exactly the same thing that we generated earlier manually. To do now is to return the last one using the minimum number at. And now if we go back and grand again, we're going to get two as the minimum number of changes that we need to present a specific number. However, if for example, we don't have this. Suppose we have five. In this case. Suppose we have 678 as belts. What we're going to get is actually infinity and this is not a correct answer. We need to return minus one. In this case, we simply need to check if the minimum number at n is equal to infinity. Now this is the case. We're going to update it to minus 1. So there's multiple ways. So for example, one way to do as if this minimum number is equal to infinity, but we don't do is to simply return or updated. So if it is equal to infinity, we're going to, I'm sorry, we need to add the brackets so the minimum number at n is equal to infinity. We're going to update it into minus 1. Now if we go back and hit refresh, we're gonna get minus 17 f infinity. Another way to do that is to simply check alongside the return statement. So to do that, we simply check if this minimum number is equal to infinity. If this is the case, we need to do something. And to do that, we simply write this question mark and then we have two options. So this statement is satisfied. The first option will be, so it looks something like this. So if this equation is satisfied, if it returns true, we're going to get this option. Otherwise we're going to get the second one. So if this is true, but we're going to do is to return minus1. Otherwise, we're going to return the minimum number at Penn. And let's check it again. If we go back and running again, we're gonna get minus1 as before. Now, for example, if we have this right here as tan, and let's go back, run it again. And of course, it shouldn't be, should be multiple of six, for example. Now, if we go back and run, we're going to get two as the minimum number of changes that we can have using this 12 and these bills as the amount. So that's it basically for this implementation. This is how we can implement it in JavaScript. That being said, this is the end of this video. See you in the next one.
10. Minimum Number Python Implementation: Okay, So in this video, we're going to do is to create the Python function for our pseudocode that we came up with earlier. So let me just add a few things right here because the deleted. So what we're going to do is to determine the minimum function of this one right here. So let me just make bigger. So we have $7 and the changes or deepest that we have are 1, 3, and 4. So to do that, Let's start with defining our parameters straight away in Python. So n equal to seven. And we have this list which is 134. And these will represent people's soap dels equal to 1, 3, 4. Now we can start with our function. So what we're going to do is at first, we need to create this minimum number list and it should be initialized to infinity. And after that, what we're going to do is to add or modify it each and every time we pass through every one of these elements. So what we're going to do at first is to create the actual list by simply adding or naming it minimum number. And it will be equal to a less than in this case, what we're going to do is to fill it in with him. And how we can do that, we can simply pass through a for loop in range of n plus one and then fill it, fill the minimum number that we're going to append to it. Float, indicating that this is an infinity. So now a free go ahead and print it out. We're going to see that. So if I go ahead and print this one out, we're going to get these infinity as the elements in this list. Now, to start with, let's go back right here and let's see our function, our, our pseudocode. Now remember that we need this one, which is the first one which will be equal to 0. So before doing anything, let's just make it equal to 0. So minimum number at 0 to be equal to 0. Now we can go through our code, so let me run it again right here. And as you can see, the first one is 0 and all of the rest are infinity. So what we're going to do now is to pass through 24 net nested loops. And while doing that we are going to pass through all of these and then update all of these. So let me just created so for Bell and belts, we're going to start with those and then we're going to go to the minimum number. So to do that, we can simply create a second for loop using a range of the length of this number. So it's for the amount and range of the length of this actual list that we created. It's the minimum number. And what we're going to do at first is to check if the amount is greater than or equal to the bill. In this case, if this is the case, we need to update it. And it is one of two things according to our formulas. It is the minimum between the actual minimum number amount and or one plus the minimum number at amount minus spill. So let me just implemented right here. How do we do that? So it's minimum number at the amount should be equal to two things. The minimum between the minimum number amount and minimum number 1 plus the minimum number at amount minus the, that's it. Basically, this is how we can implement it. Now if we go back and let's hit refresh and run this code again. As you can see, we got 0, 1, 2, 1, 1, 2, 2, 2. And if we look at it here, we got 0, 1, 2, 1, 1, 2, 2, 2. So it's the exact same result. Now keep in mind this is not what we actually need. The actual solution of this problem is to get the last one right here. So we're going to return the last one from here. Now, one thing we need to pay attention to is that maybe some, there is no such combination that allows us to get the specific number. So let's suppose that we have the $5 and all of the denominator, all of the best that we have, our 678. So in this case we can represent five using any of these bills. So the answer will stay infinity. Now in this case, if the answer is infinity, we don't return infinity, we just return minus one, indicating that there is no solution for such problem. In this case, we need to pay attention and make sure that we get this edge case. So how do we do that? We can simply create an if statement if the number of coins. So if the minimum number is the amount, or maybe if the minimum number at the last one, which is n, is equal to infinity. What we're going to do is let me just try to flow tried here. And if this is equal to this number, what we're going to do is to return minus1, minus1. Otherwise, we're going to print the exact number, minimum number at. And so that's it. Basically this is how we can do it. Now if we go back, hit refresh, and run this code again, think we have an indent does not match the other. All right, so let's fix it real quick. We're going to do is to make it like this. And now I think we're good If we go back, run it again. And the answer would be two. Now in this case, if we have the example that we said about earlier, we have 6, 7, and 8. If we go back and refresh, we're gonna get minus one, indicating that there is no way to get this amount using these three types of bills because they are bigger than five. So that's it basically for this problem, this is how we can be met with Python. That being said, this is the end of this video. See you in the next one.
11. Number Of Ways To Return An Amount : All right, so in this example, there are going to go through another problem, which is the number of ways that we have to make a change for a specific amount. So suppose that we have a $5 amount that is right here. And what we're going to do is to compute the number of ways that we can represent this five-dollar if we have these bills right here. So if you have 1.2.34 bill, and in this case, what we're going to do is to use dynamic programming to have the most optimal solution or the exact number of ways we can compute using these bills to have this $5 amount. So to do that, let's start with creating the list that we're going to need. And as we said before, this five-dollar, we're going to create a list that can make up to $5. So to do that, we're going to have the size of this list as five plus one, which is six. And this case, let me just create this list right here. So we have 123456 elements in this list. So the indices are as follows, 012, day 4 and 5. So these indices represent the amount. So let me write it right here. I'm sorry. So here we have the amount. And what we're going to have here is the number of ways. So I'll just denote it as number of ways. So what we're going to do is to go through all of the base that we have one-by-one and then check the number of ways that we can represent this five-dollar using these Belk right here. So first of all, what we're going to do is to initialize all of these to 0. So 00000. However, the first one would be the base case. And it's safe to say that this one should be initialized as one. Since if we think about it, if we don't have oh, we have a $1 or $2 or three or $4 bills and we need to present the amount of zeros. There's only one way to represent this amount by simply not having or not using any of these amounts. So it's safe to say that we can use the number of ways as one for the amount 0. Right? Now, if we look at it, Let's start with this one right here. So let me change the color. So now we are working with this $1 bill. So how many ways can we represent the amount of one using a $1 bill? And it's pretty straightforward. We can represent it by one way. So instead of having 0 here, we're going to have one. Now, let's move on to the $2 amount. How many ways can we represent these $2 amount using this $1 bill? And of course it's the same. We just have one way that is to use 2 $1 bills. Same thing here. So we're going to have 111. So what we're saying is that we can represent this 34 or $5 amount using $1 bill in one and only way. And this is to use, for example, here if we have $3 amount, so how we can, how can we get this $3 amount? We can use 3 $1 best from here. And it's the same thing for 4 $5. Now let's move on to the second one. That is, we have this $2, but now what we're going to do is to simply skip 01 amount since we can to present these amounts using a $2 bill, because two is greater than 01. So we're going to go all the way to this $2 amount. Now, let's think about it. What do we have? We have these $2 amount, right? And this we also have these $2 bills. So we can represent these $2 amount using 1 $2 bill from here. And of course, we don't want to forget that we can represent it in one way using this $1 bills. So what we're going to do is to remove this and add two right here because we can represent it now in two ways. And we're going to find out the formula in a bit, but let's work it out now. So for example, now we have this $3 amount. So what we're going to do is to also represented in two ways, right? So let me write here too, and let's think about how can we represent this amount three. So if we have $3, we can either use two, uh, 3 $1 bills. So 3 times 1 or 2, or 1 to dollar bills and 1 $1 bill, right? So 12. Bills and 1 $1 bill. And we're going to get the amount that is three as before. Now, if we go back to here and let's find out how many ways can we represent this amount for. So if we have $4 and we're going to need either for $1 bills or to two-dollar bills, or 1 $2 bill plus 2 $1 bills. So if this makes sense, it's okay if it doesn't, let's think about it that we have here for $1 bills. And here we have, or we have to, to dollar bills, or we have 1 $2 bills and to $1 bill. So all of these will be the same as you can see here. If I draw it. We're going to have here too, and here, the same thing and we have for $1 bills. So that's it basically. Now, let's think about the formula. How can we get that? We have three ways here. So we have three possibilities to represent this number four. And instead of having one here, we're going to remove it and add three. So if we think about it, we can see that if we have this $2.2 dollar bill right here, what we actually did is that we added one to the number of ways that we had into. So to make it clear, let, let me just write the formula right here. So what we're saying is that we need to update this number, which is number of ways at a specific index. Suppose it's ad I. It will be equal to one plus the number of ways. And let me delete all this. And it is the number of ways at this specific amount, which is four minus what we get from here. And we're going to name this, this list as bills and denote each and every one of them as the bill. So it's amount minus belt. So in this case, if we're going to look at this example, we are at the mountain before and the build number two. So what we actually did is that we added this one from here. So here it's not one, it's the number of ways. So it's plus 0 equal. And let me just delete this. So it's actually equal to this one number of ways at I, equal to number of ways at i. So what we already have, the actual number of ways plus the number of ways. Let's hear this number of ways at amount minus bills. So this is the formula that we're going to use now if you use it right here, Let's think about it. We already have one here. So the number of ways at, I write here, it will be equal to the one plus number of ways at 4 minus 2, which is equal to 2. So if we go back to the index to going to see that we already have two here. So we're going to have 1 plus 2, which is equal to 3. And this is what we got using the thinking or using the example that we did before. So we found out that we have three ways to represent this four. We have 1 $2 bills. Now, let's move on to the last one which is five. And using this formula, we can compute that if we have the $5 amount and we have this, these tuples, we can have one way plus the number of ways at five minus two, which is number of ways at this index right here, three. So it's two, so 1 plus 2 will be 3. Now, if we do the exact same thing for the 34 we can get. So let me just change the color. Let me just make it blue ink it easier. So what we're going to do is just crop these from here and paste them here. Let's delete this and Let's continue. So what we're saying is that now we are at three. So as we said, we can skip 012 because they are smaller than three. We're going to go all the way to three. And now what we're going to do is to say that we can represent this Amar three using two ways plus the number of ways at three minus three. So this amount minus this three right here, which is the belt. And if we go to the number of ways, three months today is at 0, so we have one. So instead of having three right here, we're going to have 2 plus 1, which is 3. Now we're going to do the same exact thing for this one. So it's 3 plus the number of ways at amount minus mil, which is four minus three, which is actually one. So we're going to change this into 3 plus 1, which is 4. Now we're going to end up with this file, which is we have 3 plus the number of ways at amount which is 5 minus the number of words, number of bells, or the actual belt, which is great. So 5 minus 3 will give us 2. And we're going to look at to have here the number of ways, which is two. So we're going to update this into three plus two to five. So I hope this makes sense. We're going to continue with this final one, which is four. Now we have the four bill amount to dinner just computed for these two because it doesn't make sense to have this four into 0123 since they are smaller. So what we're going to do is to take this 4. We have this four, which is the number of ways at I plus the number of ways at amount minus 12. So 4. This is the amount minus before Bill. So we're going to get the number of ways at 0. So we can see that it is four plus one is five. Then we're going to take this five right here. Plus the number of ways at amount minus well, which is also at one, because number of ways of 5 minus 4 which is equal to one. So number of ways at one, going to check that it is equal to one. So we're going to update this to five plus one. We're going to end up with six. So that's it. Basically this is how we can get the number of ways using the dynamic programming method using this specific amount. Now what we're going to do is that would look, if this is the exact this is the correct number of ways. So if you have this $5 amount and we have these four types of Bill, what we're going to do is to represent this file using these manually. So let's think about it. We can either have four or 5 $1 bills, or we can have 2122 doubles plus 1 $1 bill. Or we also can have two or 1 $2 bills and 3 $1 bills. Or we can also have 32. So 1 $3 bill and 23 dollar bills and 12 dollar business side. Or we can also have and 1, so 1, 4 dollar bills and 1 $1 bill. So these five or we can also have the 311, so 13 dollar bills and to $1 bills. And this if we count them, 123456. So we'll end up with six ways to represent this $5 amount using these four types of people. So I hope this makes sense. In the next video, we're going to simply write the pseudocode of this and then we're going to implement it in our languages. So see you then.
12. Number Of Ways Pseudo-Code: All right, so in this video we're going to do is to summarize our thoughts and actually write a pseudocode that we're going to use when we implement this magnitude, this algorithm now code. So let me just delete all of these. And of course all this also. So now we can continue. Now let's think about it for a second. So what we actually did is that each time we're going to use a work with a belt. So let me just write the pills here fast. So each time we're going to work with a bill from here, we're going to add or update this number of ways. So what we're going to say is that if the amount is less than this actual bell, We're gonna not gonna do anything. We're going to just skip it. So the pseudocode should go as this. So the first thing we're gonna do is to check if the amount is greater than the belt. But this is the case. We're going to continue. So the amount is greater or equal to the bill that we have. We're gonna do something. In this case, what we're going to do is to update the number of ways at this actual belt, right? So what we're going to do I'm sorry, at this actual amount. So what we're going to do is to update the number of ways. And this case, it will be at the actual amount. We're going to update it into. It will be equal to two things added together to be equal to the actual number of ways that we actually have right now. So it will be equal to number of ways at amount. We can add something new, which is the number of ways at amount minus one. So it will be equal to number of ways at amount minus the bell that we have. Now, if you want to make sure that this algorithm actually work, Let's just do that, for example, at four and lets you use the last one right here, which is also the bell for. So what we're going to do is let's assume that we have here for. So we are now at the stage where we have the number of ways, which is four and we are going to update it. So we're going to look if the amount is greater than or equal to the bill. And this case the amount is four, which is equal to four. So this actually work. What we're going to do now is to update the number of ways at the specific amount. So number of ways at four would be equal to number of ways at four, which is four plus the number of ways at amount minus spill. So the number of ways at amount my spell, which is 4 minus 4, to be equal to 0. We're going to go to the number of ways. Take this one added to the 4 will give us 5. So now we can, we know that our actual formula right here that we generated is actually true and works exactly fine. So that's it. Basically this is deep to the court. And actually this actually pretty straightforward. Once you know the method you can come up with this pseudocode. So I highly encourage each and every time you solve the dynamic programming problem to write, write it down like this, and try and come up with a solution. And try and come up with the actual method or the actual formula that is TB used in this problem. So as the first part of the problem, we didn't know the formula would just go with the flow. So for example, here, we just said that at amount 0, we can't represented in any way other than one and only way which is don't use any amount of money. Now at amount number one, we can represent it if we have this $1, but we can represent it by one. And here the exact same for the others. And then it wasn't until this amount number three that we knew the formula. I'm sorry. It wasn't until the sum of number four that we knew that formula. And we computed using this example right here. So always start with an example and try to come up with a formula later. So that's it. Basically, this is for the pseudocode. At the next video we're going to implement it and our actual code. To see you then.
13. Number Of Ways Java Implementation: All right, so in this video we're going to implement our function, function that we came up with earlier. And I already instantiated this method public static int number of ways. And we got two parameters. The first one is the actual amount denoted by N, and the second one is the actual bells. So this is an array of those right here. So what we're going to do is that we're going to create a new array as before, as we said before, that is to implement or to add the number of ways to each and every amount. So let me just instantiated as ways it will be equal to 0 and plus one, as we said. Now what we're going to do is to denote or add to the first one, as we said right here is the first one should be equal to one. So waste at 0 to be equal to one. And the other will be equal to 0, which are the default default number or the default way to be instantiated in an array. So as we said, we already have now one here. What we're going to do is to pass through all of these right here is from kinda pass through all of the I've built. And then of course we are going to update the number of ways right here. So let's go back. Now, if we think about it, what we're going to do is to pay the for loop, starting with 0 all the way to the bills that length and updated. And the second one, we're going to have also 0. All the way to, I'm sorry, here we can actually say that it's one. And the two will be all the way to the ways. That size dot length, I'm sorry, I and j plus, plus. Now what we're going to do at first is to check if this amount is greater than or equal to the bill. And as we said, this amount is actually in the second for loop denoted as j. We can actually change this j into amount of it will make us, make it easier. So let me just change that real quick. And then we have amount also. Now what we're going to do is to check if this amount is greater than or equal to the actual bill. And what did we say? We said this one will be noted as bills. And the actual bill bandwidth will be at best at I, which is 0, 1, 2, 3, and 4, so forth, so forth. And this case, what we're going to do is to check if the amount is greater than or equal to what will be equal to bills at. I know this is the case. We need to update the number of ways. So the ways that I, or the ways that amount some site will be updated in two ways at amount plus ways at, as we said, we're going to use the formula, amount minus this right here. So how did we get this bill? It will be the bells at I. So in this case what we said that we can compute this by using bells at i. So I'm going to simply write it right here at I and we updated successfully. Now what we're going to do is to just return the number of ways at the last one that we have. So if we go back right here, we just need this one from his. So this is the number of six. Remember that the purpose of this problem is that if we have a $5 amount, how many ways can we represent this five-dollar? And we actually did all of these to come up with the final solution, that is a six. So how can we take this? We can simply ask for the number of ways at our initial amount, which is five. And it will be equal to six ways. So that's it basically now, this is what we should return right here. So after finishing from these two for loops nested for loops, we're going to represent the ways at. So that's it. Basically this is for this problem. Now if we going to test it out, we can simply use a main function. So I'm going to simply create a main function criteria. And what we're going to do is to call the number of waves with n and bills. And before that we're going to initialize this right here. So n will be equal to the actual sample, which is five. And end bills will be equal to this actual, which is 12341. Good. Now, if we want to print it out, let me just I'm sorry. Solar system dot out, dot, print out right here. And let's run it. And as we can see here on this problem, I'm going to get six, which is the final one. Now if we want to return all of this for now, see that the last one right here. So what we're going to do is to return a list. And if we run it again, we're going to get, I'm sorry, we can't run this. Of course, we just need to create a for loop right here. So for I equals 0, I is less than the end and I pass. So I think we've got, we can print out what we got. So let me just create this place right here to be equal to number of ways. So I think we're good. We can delete this from here. And of course we can print out ways at each and every one of them. So with ADD, I simply print it out. And we're going to print it out. So at some space could continue. Now if we run it, we're going to get 11 to 35. If we go to here, we can see that we have 1, 1 to 5. Of course, we forgot the last one, forgot that it is and plus one. Now if we run it again, gonna get one, 1, 2, 3, 5, 6. And it is the same exact lesser, the exact array that we come up with using this example right here manually. So that's it basically for the implementation. This is how we can implement it. And of course, you don't need all this. This is for visualization purposes. We just need the last index or the last element in the number of ways less. That is to represent the amount five using how many number of ways using this one right here. So that's it basically for this example, see you in the next video.
14. Number Of Ways JavaScript Implementation: All right, so in this video, who can implement our function using a JavaScript. So as we said earlier, we're going to implement it using this number of ways as an array. And we can have two things. The actual amount, which is $5, and the number of beds, or the types of bells and an array or a list. So what we're going to do is to simply start with creating the function. So the function will be a number of ways and what we don't and which is the amount. And then we also have denoted by pets right here. And we can start with creating the array and name it two ways to be equal to a new array. And as we said, we need n plus one as a size. And we're going to fill it with zeros. Now, as we said earlier. But we got to do is to felt this amount at 0 by number of ways, which is one. So to do that, we're going to simply write ways at 0 to be equal to one. And now we can start with creating our two nested for loops. So going back to this example, we can see that we are going to start with a for loop, which will be for the bells. And then we're going to update the number of ways each and every time we go through one new bill. So the first one will be for the birth. For we have a variable amount or the first one will be less same it actually, and it will be equal to 0 at first. And then what we're going to do is to update it. Of course it will be until and plus one. And then we're going to build. So that's it basically. And now what we're going to do, I'm sorry, not till the n plus one. It's guilty and the actual list. And in this case, what we're going to write is Bills dot length. So that's it for the first for loop. The other one would be nested, will be variable amount, which will be equal to 1. And this case we're going to look all the way to amount which will be equal to less than and plus one. Now what we're going to do is update this amount each and every time we go through it. Now, we can start with the actual function. So what we're going to say is that we're gonna look, look at this specific right here. So if the amount is greater than or equal to bed, and as you said, Bill is not an index as we initialize it earlier, it's actually the best at this actual index. So for example, here at 0 we're going to get one, this one we're going to get 2 and so on and so forth. So to implemented, but we got to do is to check if the amount is than or equal. This bells at this index which will be built. Now to make it easier, what I'm going to do is to simply remove all this and use another method for loop which will be built of bills. So what I'm going to say is we're going to let Bill, bills. And now we can use bell and instead of this at this index. So this is another function. So what we're simply saying here is that belt of birth is actually don't do Replace bills, 0 of bills at one and so on and so forth. So we don't really need that anymore. We can just use it as. Now what we're going to do is to update the number of ways at the specific amount by simply adding this number of ways at the specific amount to a new thing. That is the number of ways at amount minus the actual bill. So this is the formula that we come up with right here. And we already said that this bill is built at i. So we're good. This is the actual formula that will continue. And now we just simply need to return the number of ways at the last index. So this is six. We just need to return the number of ways at the amount which is five. In this case, we have it as denoted as n. So we're going to simply return ways. And now we're good. I think we can work with it. This is our actual formula. Now, if we want to use it or tested, we can actually do it right here. So let's denote, let n equal to five and lead to an area of 12345. Now, what we're going to do is to print the number of ways we can create with this amount and is filled. So now if we actually tested, all right, so here we have consulted tonsillar branch. And in this case what I'm going to head over to CMD and what I'm going to use to run the JavaScript. I'm going to use NodeJS server. If you haven't installed it yet. You can go ahead and install it right now. Can simply head over to note. And as we said, can download it from here. So go ahead and download it. Then what you do is to head over to your dynamic or to your directory. In this case, I'm going to name it JavaScript dynamic programming. And in this dynamic programming, I'm going to have this number of ways amount that I created earlier. And you can simply run it from his. So I'm going to use these nodes and simply write number of ways, amount dot js. And I'm going to get six as the number of ways. Now, remember that we just wanted to have this last one. Now if we want to visualize this number of ways, less. So, in other words, we want to visualize this list such as 1, 2, 3, 1, 1, 2, 3, 5, 6. Keep in mind that we should return something else. So here we're returning ways that we can compete written ways. Now if we run it again, we're going to get this less than, that is 112357. Now keep in mind that we only need the last one which is to represent to represent this $5 amount with these four types of belt. So we have six ways to do that. So that's it basically this is it for this problem. See you in the next video.
15. Number Of Ways Python Implementation: All right, so in this video we're going to continue or incremental function using Python. So as we said earlier, we have the number of ways which is a list that we're going to store. The number of ways for each and every specific amount all the way till the end amount or the amount that we want. So do that, let's start with creating a list in Python. So let's go to our Visual Studio. And in this case, I'm going to do is to create a list. I'll name it. And it will be simply list, such as this or I can just make it square brackets. And in this case what I'm going to do is to fill this list all the way till the end, right here. So first of all, let's define our two parameters. So the first one is and it will be equal to five. And the second will be built which is also a list. And it will be equal to 1, 2, 3, and 4. And in this case, what I'm going to do is to create this list L or LastName. It actually weighs since we're going to use it as waste. And of course I'm going to fill it in with zeros. So for I in range of maybe n plus one, are we going to do is to append to this 0. Waste that append. And I'm going to append 0 right here. And of course if we print it out, we're going to get our list filled them with zeros. So if we go to here and right, by the number of ways we're going to get 000, 000, 000, and this is getting the list empty. So we have 012345 elements or five indices, which are six since we started with 0. Now what we're going to do is to third, the first one was one with one. So what I'm going to do is to simply say that at 0, I'm going to fill it with one. I'll run it again. We're going to get one right here. So now we can start with our function. We have everything ready for us. We can solve our for loops. Since we have this function, what we're going to do is to loop through all of the elements or all of the end of the numbers right here in the bells, and then do the same thing for the number of ways and updated. So I'm going to delete brand and I'm going to continue with creating a build from the bills. So now that we can continue, we can create the amount right now for this specific ways. So what we're going to do is that we're going to start from one all the way till the n plus 1. And how we can do that, we can use range of one all the way till the end plus one. And then of course we're going to open this look. And we're going to check, as we said before, if the amount is greater than the bill, we're going to update the number of ways. So how do you do that? We simply check if amount is greater than or equal to the bells or the voltage is created. If this is the case, we're going to need to update the number of ways. So a number of ways at amount will be equal, as we said, using the formula that we generated in the pseudocode, number of ways equal to the number of ways plus number of ways at amount minus minus1. So in this case, number of ways At amount equal two ways at amount plus ways at amount minus the belt. Now keep in mind that this bill is actually we're using built and built. And this will give us bells at 0, bells at I and so on and so forth. So this is just maybe a shortcut solution for the for-loop instead of having it in range of and access and bells at i for specific indices we can use bill and bells. So that's it. Basically this is how we can update it. Now what we're going to do is to simply printed out right here. So if we print ways, and now let's go back here. And as you can see, we got the same exact result as we expected one, 1, 2, 3, 5, and 6. So here this one, 1, 2, 3, 5, and 6. So we know that our program works. Now what we are aiming to do or what our goal was, to generate the number of ways that we can specify or we can create $5 in return $5 with assuming that we have only these four types of bills. So how do we do that? We simply return the last one because the last element in the list indicates that it is for the amount of 5. So that's it. Basically we just returned the ways at. And now if we go back and run it again, we're going to get six indicating that we have six ways to implement or to MD yes, to implement this function or to have $5 from these four types of bills. So that's it basically for the Python implementation. That being said, this is the end of this video. See you in the next one.
16. Knapsack Problem : Alright, so in this video, what we're going to do is to go over one of the most famous problems in the dynamic programming. And it is known as the knapsack problem. And this problem has actually two versions of it. The first one is the fractional version and the other is the discrete. Now what we're going to do is to go through an example. And we're going to discuss these two versions and we're going to learn about one of them. And it is actually been solved using dynamic programming. So to go over it, Let's start with example. The idea of this problem is that you have some items or products, and each and every one of these items has a weight and a value. So let's assume that we have four items. The first one, so I simply write them here. So the first one will be a weight five. The second will be of weight for the third will be awaited three, and the last one will be of weight too. So here we are. We have four products having all these ways. Now we need to add the amount or the value of these products. So the first one will be a value 28. So $28, the second one will be a value 20. The third one will be at 18, and the last one will be 11. So 18 and 11. Now, the actual problem is that you are going to be given these items alongside a specific weight that you can hold. So for example, let's assume that you have a bag. And in this bag you can only hold up to 10 in weight. So you need to get all of these products and add up to 10. So let's assume that you have here bag. And in this bag you can only hold ten. So now the fractional version of this problem can actually be solved using greedy algorithms. And in this case, let's see it right here. So what we're going to do is that we can take a fraction of these items in weight. So instead of taking the whole item, so we have here the weight for we can actually take fractions of this. So for example, if we want to have this from here, so we have 10, what we're going to do is to divide these amounts over the values and take the maximum of which. For example, if you have 28 over five, we're going to get something like 5.6. Let me write it right here. The second one will be five. The third one will be 18 over three, which will be six. And the final one will be actually 5.5. Now, we can always solve it using the maximum amount. So to fill these weight of 10, what we're going to do is to take all of these three from here. So we're going to take this three since they have the highest value regarding the amount over weight. And this case we're going to take all of these, so sum up to $18. Now, we're going to continue by taking this one which is five. So if we go back right here and add this five, which will be around $28. And because it has the highest value. Now remember that the purpose of this problem is to solve it or to have a weight of ten with a maximum amount of money. Now in this case we have 18 plus 28. And finally, what we're going to do is to take this 5.5. So if you remember here we have 532. Now, if we take 11, we're going to end up with something like 11 or 18 plus 28 plus 11. So this is, the weight is three plus five plus two, and it is equal to 10. Now, let's suppose we don't have a weight of ten. So instead of having a weight of 10, we're going to have a weight of nine this case. And if we are going to solve this problem with a weight of nine, we're going to end up with the same thing as before. However, don't want to have here two does two plus three plus five is nine. In this case. When we arrive to this position, what we're going to do is to take a fraction of this two. Instead of taking Net as a whole, we can take a fraction of it. So we're going to take a fraction of two. So we're not going to take all of the tool going to take a fraction, which is you can take one. And this case, the value will be 5.5. So it's 11 over 2, which is 525. Now the whole amount or the whole weight is 3 plus 5 plus 1, which is. Actually equal to nine. And in this case, we can use a greedy algorithm that searches for something or the value, the largest value that we have. So for example, here we have six, Good Take all of these. Then we're going to check if we still have a place. Of course we're going to have a place since we only added the weight of three. So nine minus three, we still have six left. We're going to take all of these. Then we only have one left. We're going to go and search between 55.55.5 is bigger and we're going to take it as the largest one. And of course we can take a fraction of it, not the whole amount. So this is the idea of a fractional knapsack. And this is actually, this actually doesn't work if we have discrete one. So imagine we have a discrete knapsack. And in this case, we can work with it because once we reach this stage here, and we have 35, then we still have one left. And this case we can't divide this one right here. So the optimal solution actually haze to use four plus five and wait. And of course we're going to end up with 48 instead of 18 plus 28. In this case. As we can see, the discrete version of this problem will need to be used to have dynamic programming as a solution for it. And that said basically for the fractional knapsack, you can always use the greedy algorithm with it, but we don't treat the trait now we actually want to just work with the discrete version where we have the dynamic programming. So let me just delete all of this from here. Now, for the discrete version, we also have two versions here. We have the unlimited quantity and the limited one. So here when it is known as without repetition. Now, let's talk about it for a second. For the unlimited quantity, they mean that we have unlimited amount of this item, this item, this item and this item. However, until limited quantity, which is without repetition, we only have one of this item, E1, product of this item, one of these and one of these. So we can't really use this one more than one time. Now, what we're going to do is that we're going to have an example and go through the unlimited quantity alongside the limited or without repetition one. So let's think about it for a second. If we have this example right here, let me teach you. And let me actually take all of these and make them smaller and come to here. And I'm going to do the same exact thing for this also. And I put them here. Now, we can continue our work. Now let's imagine that we have unlimited or the without the petition, one that sat with the, without the repetition. So without repetition what we're going to do. So here we have Without, we're going to take this three, which is the highest one. So again, take this three. Now remember that we need a weight of ten. So we have this three plus this one, plus this one of five. Now if we want to add all of these, so here we have 18.11.28. In this case, we're going to end up with $57 as a final value. And it will be the highest one for the without the repetition LFO. And just compute this 13 plus two plus five, which is equal to 10. So we're good now with unlimited quantity, but we can do is, so let me just change the color right here. So here we have the unlimited. Let's give it a look. So imagine that we have more than 13, so we have 3 plus. Can also use another three, which will add up to six. And we can also use two twos in this case. So now if we compute it, so here we have three plus three, so that three is $18. Here also 18, we have 11 and 11. So as you can see, this will turn into $58, which will be better than the old one if we have unlimited quantity. And assuming that we have the same number or the same weights and the same amounts. So in this case, as you can see, it's better to use the unlimited quantity or the width repetition right here. So these are the two versions that we have in the discrete version of the knapsack problem. And we're gonna focus on them. And we can also solve them using dynamic programming and the next couple of videos. So see you then.
17. Knapsack With Repetition : All right, so in this video we're going to focus on the discrete with unlimited quantity of version of the knapsack problem. So to do that, let me just delete all of this from here. And he is also an indicators. And let me take all these and make them smaller and put them away right here. And I do the exact same thing. This sort let me just take them and place them right here. So now we can start with our knapsack problem with repetition with unlimited quantity or items. So in this case, if we want to look at, look at it, that way, we're going to end up with something that is equal. So here we have $58 in total. So keep that number in mind for data. Now what we're going to do is that we're going to use an array or a list to try and solve this problem and come up with a proper solution using dynamic programming. So what we're going to do is that we're going to take the amount or the maximum weight that we have, which is 10, and create a list, ten plus one as a size. So let me just create, and this is our list. And what we're going to do is that we're gonna update all of these, each and every time going to pass through them. Now let's think about it. What we're aiming to do is that we can, we need to have the maximum amount of money using these, assuming that we have 10 as weight. So we're going to use all of these. We have a limited quantity and we're going to use unlimited amount and we need to find the maximum amount of money. Let's start with 01. As high as we can see, we don't have anything and we're not using fractional, so we can divide this. So what we're going to do is to simply write 00 here. Let me change the color. Now we have two and as we can see, we can use to, and the cost will be $11. Now remember that we need to maximize discussed for now, we can't use anything but this 11 for the two. Now if we go all the way till 2, 3, and let's look at the three. We have $18 which is bigger than 11, so we can work with 18 right here. Excuse me, let me write it better. So we have three, which will be a total of 18. Now if we go to the fore, as we can see for the, for one, we have here the value of 20. Now in this case twenties bigger than 11 and 18. So we're going to write 20 here. Now if we go to the five, we actually have more than one option. In this case, let's look at it. We either can have two and add to it a three, which will be 11 plus 18, which will be actually 29. Or, I'm sorry, or if we have three and we add to it, two will also get the result of 29. So what we're going to do is to simply write here 29. So keep in mind what we did is actually using either 2 plus 3 or 3 plus 2. And we're going to get 29. Now as the sex, the total value or the maximum value that we can get to be 3600. Explain it in a minute. Mile, think about it that way. You can also have all these information right here. So let's think about this five and this five. Keep in mind that this file is the optimal solution for the maximum amount, which is 29. Now think about it as if we have a five and we're going to add one to it to make it a weight of six. And this case, there is nothing that we can add to make this way more than 29. And in this case we're going to look at four. So let's look at four. If we have 20 right here, what can we possibly add from here to make it bigger than 29? In this case, if we look at it, we can add two from here, which has the value of 11. So 20 plus 11, it will be equal to 31 Nazi. Now let's think about this trip. So we have three. What can we possibly add to three? To have sex as an amount was or as a weight. In this case, what we can add another three, which will also total to $18. So 18 plus 18 to be 36, which is bigger than 31. So we're going to delete this and you're going to use 36. Now we're going to also go all the way back to this too. So we're going to ask ourselves the same question. What can we possibly add to, to, to make it six? And luckily we have this four right here, which is the value of 20. So if we want to use it, we can add the value of two, which is 11 plus 20, to give us also 31, which is not the optimal value, already have an optimal value that is 36. So this is how we can compute this. Now, moving on to the seventh one, and as we can see, we have 36, but we can't add anything to it. So if we want to use it here, we can. So let me just try that for now, 36. Now if we go back to this file, if we have 29 and we add this two to it, so five plus two to give us seven. So 2029 plus 11, it will give us actually 40, which is bigger than 36. So we're going to use it. And of course we can go all the way back to the 4, 3, and 2, but this is the optimal solution and you can try it by yourself. Now let's move on to the aid. This aid, the optimal solution will be 47 and it will be actually 36 plus this one from the two which is 11, so 36 plus 11 is 47. Then we're going to have the optimal solution for the weight of nine, which is 454. And finally 58 for the last one, which is actually using this edge from here, the optimal solution of eight plus adding to it this two from here, which has a value of 11, so 47 plus 11, which will give us 58. And as you can see, we got the same exact result as before. So that's it. This is how we can get the maximum amount using the dynamic programming method. I know that if you are going to solve the knapsack problem, and if it has a small problem, can solve it just by head. You don't really need to this one. But what happens if you have maybe 10 or 15 products or items right here? You can't really just think about it and come up with the proper solution. So this is the correct way. This is how we can compute it using the optimal solution that we can get. So that's it basically for this video. And the next one we're going to write pseudocode. And we're actually going to come up with a formula that we used right here. So that being said, this is the end of this video. See you in the next one.
18. Knapsack With Repetition Pseudo-Code: Alright, so now that we have an idea about the knapsack problem with repetition, Let's take about or come up with an actual formula or solution to this problem in a form of pseudocode. Now in this case, what we're going to do is at first define our parameters. So what we're going to get actually is three or four parameters. I'm going to talk about them. So the first one will be actually the weight that we're going to need. So what we're going to do is to type here w. So this is the first parameter. The second one will be the actual values such as 54, I'm sorry, such as 282809, 11. So this will be an array. So in this case, I'll just denote them by Val. So it's a list or an array. Now, this third one is going to be the actual weights. So I'm going to just try and width. And of course it's going to be another list array. And of course the final one would be the size of the length of this file and weights. So I'll just denoted by n. All right, so what does this stand for? So Val and waves should be the same. For example, val at 0. We have, in this specific example, we'll have the value 28 and waits at 0. We'll have the value of five. So this is how we can access them since they have the same index. So 28, 524, 18, 3, 11, and 2. So this is a, basically this is what we're going to get now, let's think about it in a dynamic programming way. So the first thing we're going to do is to create this array, right? And the semi actually is of size w plus one, as we said. So I simply denoted as a denoting that is the maximum capacity that we can get. So our array will be MA, and of course its size should be. So this is the array or the list and of size Tune be this weight plus 1. So w plus one. Now recall that when we had the stamp as weight, we created this array of length ten plus one. So this is length 11, all the way from index one, index 0, I'm sorry, till the end of index 10. Now, this is our array called MA. Now we can start formulating or going through two nested for loops and updating these values right here. So let me just list some of these. Delete this. I'm going to take all of these and make them smaller. I think we don't really need them for now. I'll simply just add them right here. Now the second one will be this. So this is the first thing we're gonna do and our code. Now remember that what we're aiming to do is to create a list or an array that holds the optimal values for each specific weight. For example, the optimal value here for this weight of 0 is 0. The optimal rate of one is 0. The optimal weight of 2 is 11, and so on and so forth. So of course, when we get to this point, and that is the six. And we used the screen from here, we use 18 plus another 3, which is 36. We knew that this is the optimal way that we can get for this value of three. And of course, this is very important because the values are dependent on each other. So for example, if this is not the optimal way for this value of three, and we used it in sex than, therefore, this six is not the optimal way also. So that says, this is the idea behind it. We just aim to make the optimal way for each weight all the way to the end. And of course we'll end up with an optimal way also. So what we're going to do now is to start with our for loops. The first one, we'll go from 0 all the way to the end of this weight. So it will be from 0 till W. Now, of course this is capital W. And then what we're going to do is to go and another for loop. And this formula will be a value j. Now this j will go from 0 all the way till end. So I'll talk about it in a second. Now if you think about it, what we are doing basically is that we're looping through. All of these one by one. And each time, for example, if you are a two, what we're going to do is to look through all of these right here. So we're going to look through 5, 4, 3, and 2. So these weights should, we should access them. And we can also access these values using the valid we talked about earlier. So that's it. Basically, we have our Val and wastes and we can access them inside these two for loops. And what we're going to do is to check if this weight at a specific index of j, right? So limb, remember that we're loping, looping through this with j. So this way, at a specific index is less than or equal to the actual weights that we are going through, then we can do something. Otherwise we, it doesn't really matter and doesn't make sense to change. So for example, let's go through one of the examples. Let's suppose that we are at one right here. What we're going to do is to loop through all of these. Now what we're going to say is if this five is less than or equal to one, then we're going to do something. Now. Recall that five is not greater than and not less than one. So what we're going to do is to simply ignore it, since we can represent the S1 dissuade using these five. Now what you're going to do is to pass through all of this so far, 432. And we're going to see that they are not less than one. So of course we're going to ignore it, so the 0 rest as they are. Now what we're going to do is to go through another example. Now, we are at I equal to two in this case, this is i. So let's ask ourselves if this two is less than five, I'm sorry, if this two is greater than five, it is then not gonna do anything. This two is greater than four or three. No. Then is this two is greater than or equal to 2. Yes. So we can use this to here. So we add the value that we have here, which was 0 actually added to this value from here. So that's it. Basically, this is how we can do it. Now, let's try it with the last example. So for example, let's suppose that we are at four. Let's ask ourselves so it's 4 greater than 5? No, we can't use it. Is for greater than four, greater than or equal Actually, yes, it is. So what we're going to do is to take this 4 and access it. Of course, using the, so for example, we are here at this for what we're going to do is to write, let me write the formula. So what we're going to get actually is that we're gonna update this value at four into something else. That is MA, at the weight that we had. So this is the way that we are working with minus the weight that we're going to take. And in this case it is before. Of course, this is not defined formula. We're going to need to add to it this value here from default that we get. So it is plus 20, I'm a f at 0 actually. So this is 0 MA at 0. We're going to look at it and it is 0. So 0 plus 20, we're going to get 20. Now, let's think about it for a second. What did we do right here? Well, if you actually did, is that we are at weight for now, remember that you need a weight of four. And of course, if you're going to get the weight of four from here, you actually need to be having 0 weights and add to it this four to be a 284, right? So for example, if you're going to add the weight of three, you're going to need to be having a weight of one, then add to it three, we get this weight of four, right? So that's it. Basically this is how you can compute it. You just think about it that if you're going to add this weight of four, where would you rather beam at before to arrive to this position right here? And the actually, the, the actual solution is pretty straightforward. You should be at index 0. Add to it this four. From here, we're gonna get to him. So this is why we're adding this value from here into the one from here. And then we're going to have it at 20 right here. So that's the idea behind it, is how we can gather. Now let's think about another, another loop. So now let's suppose that we are at three. We're going to ask ourselves if four is greater than or equal to three. Yes, it is. What we're going to do is to take MA at four. We're going to update it. Of course, we're not going to if it's less than this actual 20 from here. Of course. So we have here our 20. Now, let me just show it right here. So here we have, we already had 0, right? Now, we think about it as it's 20 greater than 0. Yes, we should update it. So here we have 20. Now if we are at this tree, what you're going to do is to ask ourselves, is it greater than four? I'm sorry, It's great for greater than or equal to three. Yes, it is. We can update it. Now we need to check the value. If it is greater than 20, then we can update this one. If it isn't, then it doesn't make sense to update. Now let's look at it. What are we going to do? So we say that MA at four should be equal to MA at this four minus three plus the value that we get from here, which is 18. Now the value at M, a four minus three, which is a 01, I'm sorry, is also 0. So we're going to add 0 plus 8, which is equal to A1. Now we're going to check if 20, less than 18. No, it isn't. So we're gonna keep the sweat 20 and ignore this one. And of course we are going to continue. So we still have this one left. And of course we're going to say that MA at, for maybe equal to MA at 4 minus 2 plus the value that we had a which is 11. All right, So is this the case? So I'm a at two, it's actually 11. So we're going to get 11 plus 11, which is actually 22, which is also greater than this 20. So we can update it right here. So that's it. Basically this is the whole idea about it. This is the general idea about this knapsack problem. Now what we're going to do is to simply make it look better and absolute code. So we already have this formula here, but happy, just deleted and write it again. And nice way. So what we're going to say is we're looping through all of the weights. Then we'll looping through all of the waste from here for each way that we have in our array. And we're going to check if the weight from here at this specific index. So weights and j than or equal to the way that we have here, which is I. Actually. If this is the case, then we're going to update something. But we're going to update is actually the way that we have MDMA to create it. So MA and this specific index, which is I, should be equal to the maximum between two things. So it should be equal to the maximum between the first one which is MA at i. So it is the maximum between itself or the MA at I minus the weights at j. Of course, after finishing from this, we're going to get to add the value which is in the array val from here. So we're going to add a value at j. Now let's think about it for a second. In this case, what we're going to say is that we are, if we are at this for, for example, and we are here at this four. So four is greater than or equal to four. This is it with a J, which is how we access the score, is 4. This one is greater than or equal to the weights at j. Yes, we're going to update them a at four. In this case, the MA at four, it should be equal to the actual value and the MA at four, or the MA at four minus four, which is 0, plus the value at this specific index, which is 20. So that's it. Basically this is the formula. And of course, you should always start by thinking about the array that you designed before, then come up with an actual solution. Tried to think about how we use the values from before and our actual indices here. And actually, you really need to pass through all the examples to see the actual pattern of this formula. So that being said, this is the end of this video. See you.
19. Knapsack With Repetition Java Implementation: Oh, okay, so in this video we're going to solve the knapsack problem with repetition. So the first thing I'm going to do is to create a function. So it will be public, static. And I'm going to name it knapsack. Then we're going to get the parameters to the first one should be the weight, as we said, the second one should be the length of the values and the items. Then we have the value, values, and then we have the weight. Now, let's open it up. And now what we're going to do is to create our actual list. That is the, MA. We're going to define it as an array. In this case, an intimate. And to have signs of W plus one, we said. And of course, by default in Java, all of these should be zeros. So we don't really care about setting the first one to 0 and so on and so forth. So we can skip this and start directly with our for loop. For the first one will be at I equal to 0 and all the way to the end and incremented. Then the second for loop should be half j. And in this case, we're going to go all the way to the end of the values and weights. Then we're going to update it. And of course, what we're going to do now is to check if these weights is less than or equal to the ways that we're going through. Then we're gonna update the value inside this formula, inside this list. So this is it. We're just going to use this one that we used before. So let me just go back and write it down here. So if weights at j is less than or equal to the weight or to the eye. Now remember that I stands for the weight, the actual weight. So if we are at I equal to four, this means that we have, which is, this is the way that representing. Finally, we're going to end up with the final way that we need, which is ten. And this is what we actually are aiming for. So if the wait, I'm sorry, we have a typo. So if weights at j is less than or equal to, I, can update PMAs for mayor tie should be equal to maximum between two. So what we're going to do is to use Mad Max. And of course we're going to use it. Either I'm a at i or something else that is at i. As we said, five, we just subtract the weights at j. And of course we're going to add the value from the values at j. So that's it. Basically this is how we can update it. And here we have a typo. Let me just clear it out. They said basically this is our formula, this is how we can update it, just use this formula from here. Now what we're going to do is to simply return the last ones in the list. So return an a at the actual weight that we want. Now let's use it right here. So at simply create a main function, I'm going to just define some parameters. So let's suppose, let's use the same exact problem or the same exact parameters from here. So we have the weight equal to 10, then we have the values which are 5, 4, 3, and 2. So it is a lesser an array. The values should be 5, 4, 3, and 2. Then we're going to move up to the actual weights, which are also I can just copy that from here, 28201811, so 2828 and 11. Then we're going to end up with the values that length. And of course, this is, of course what we're going to do now is to call the actual function. So let me just print out right here. So system dot out, dot print to print actually is the knapsack. So I'm going to call this function right here with, alongside the following parameters, so w values. And now what we're saying, well, we have a problem right here. Let me just check it out. Method. It's not a playbook. Okay. All right. So we just forgot them. We should add this desolate Basically now if we go ahead and run this one. So we got 0, let me check values and weights out. Okay? So i, okay, so here we have weights and you will have values. Is just switching done by mistake. Now if we run it again, we're going to get 58, which is the exact same result that we came up with here and here. So we saw that using three ways. The first one is using our thoughts and just thinking about thinking about it. Then we use this one and we got 58. And finally we used it in our code. So most probably this is the correct way. Now, what we're going to do is to just visualize it one last time. We're going to visualize the whole array. So instead of returning, just call one, I'm going to return an array. And of course, I'm going to create a for loop, right? Yeah. Sorry. So for too long to do is to iterate through all of this. So I'm gonna name it also here, MHC2, and I'm a knapsack of W and values and weights. Now go all the way to be a length. And of course we're going to print them out. So I'm going to simply print out and with subspace of your run it again, we're going to get the same exact thing that we got from here. So we have forty seven hundred fifty four and fifty eight. So they said basically, this is for the knapsack problem using Java.
20. Knapsack With Reptition JavaScript Implementation: Okay, So in this video we're going to solve the knapsack with manipulation problem using JavaScript. So the first thing I'm gonna do is to create our function. So the function and name it Knapsack. I'm gonna get the parameters so we have to wait the length of the items. You've values and E. Now let's open it up. Now, we're going to do, is to actually create this method or this less stretchy and a. So let me go back and let him a new array of size n. We said the size should be the weight that we have plus 1. Now what we're going to do is to fill it with zeros. Then we're going to start with our two nested for loops. So let I equal to 0, I is less than or equal to the weight. And I plus plus. So we're not doing anything but this B is discussed here, so we're just getting these two for loops. The first one from 0 to w, The second one is two. And so that N1, we have j equal to 0 all the way till the end and j plus, plus. Then we're going to check if the weights that we're dealing with are actually less than or equal to the waste that we are at this list. And this is the case, then we need to update it with are just coming to do this in JavaScript. So if weight at the specific and that's less than or equal to the index, I soften it up. We're going to update the MBA at I should be equal to the maximum between two things. Should be equal to the maximum between itself. Or I'm at I minus P waves. As we said earlier. And of course we're going to add the value from the values list at i j also. So there's a, basically this is our actual function. Now what you're going to do is to, after finishing from these two for loops, going to return the MA at WWW. Now, if we are going to just try it out, let's run it. Let's define actually. So let w equal to 10, gonna take the same exact example from him. So w equal to 10, we're going to have values that are equal to. The actual value is 28, 2018 and 11. So values equal to 2828 and 11. Then we have the weights. Weights equal to it is equal to actually 5, 4, 3, and 2. Then we're going to have n, which is values dot length. Then what we're going to do is to actually call the function alongside these parameters. So W and values and weights. And of course we're going to lay it out. So console log. And we get after we going to do is to actually just up and down command prompt. And then I'm going to head over to my directory inside this task desktop, I have JavaScript right here. I'm kinda copy this and head over to it. And then I'm going to run this problem using node. So node knapsack with repetitions, the ab.js and we got an a and as a result, indicating that this is not a number. So let me check it out. Everything looks good for hair and maximum. So the problem is, okay, so the problem is right here. So we have, we need to close it as a plus. Just so this is the actual formula. Now if we go back and Annette again gonna get 58 as the maximum number that we can get from this formula. Now what we're going to do is to actually print all of this out. So instead of having just the last one, I'm going to just for the sake of this problem. So as we can see regards 000 011, 1822. And if we go back here, we can see 000 011, 1822. And of course, it's all the way to 2936404912, which is exactly a 293640 forty seven fifty four fifty eight. So with that, we can make sure that our problem works and we got the same result as the one that we performed manually right here in this list. So that's it, basically this is it for implementing the knapsack with their petition using java script.
21. Knapsack With Repetition Python Implementation: Okay, So in this video we're going to solve the knapsack with repetition problem using Python. So the first thing I'm gonna do is to create the definition or the function. I'm going to name it knapsack. And alongside the parameters that we're going to use. So wn values and weights. Now let's open it up. The first thing inside this function, we're going to visualize the actual list array which has MA, organism it, MA, and who cannot have it in range of. So it will be of zeros and it will be for I in range of w plus one. So this is how we can create this list using one line of code in Python. Then what we're going to do is to start with our two nested for loops. So for I in range of W, swan, we're going to create another for loop, which is for j in range of AMP. Then we're going to start with the condition. So we didn't do anything for now. We just created these two for loops. Now we're going to check if the weights at j is less than or equal to I. So if weights at j is less than or equal to i, we're going to update the AMA at I. So I may add, I should be equal to one of two things. It is the maximum between the actual value that we have, or the maximum or the other, which is MA at Pi minus weights at j plus the value of j. Now let's go back and write it down. So max at either MA at or the second one, which is MA at weights at j. Then of course we're going to add to it the values at j. So that's it basically. Now what we're going to do is to simply return the MA at the last one, which is at w. Since we're gonna just need this one from here. So we'll just return it as it is now to try it out, let me just create your things. We're going to use the same exact example that we used here. So w equal to 10, the weights are 5432. So weight equal to a list of 5432. Then we have the values which are 28201811. Then finally, we have the length of these values of weight. Now what we're going to do is to call this function and print it out. So you can simply print this knapsack alongside these W values and weights. Now if we go here and run it, so I'm going to type Python alongside knapsack with repetitions and run it. And we're gonna get 58 as the maximum number allowed for this specific example. Now to visualize the actual list that we created here, let me just print instead of MA and then I return and a, the whole list instead of returning the last item. Now if we go back and refresh and running again, we're going to get 0011182258. And if you compare them, they are exactly the same as the example that we did before. So 01118, twenty two twenty nine thirty six forty, then forty seven, fifty four and fifty eight. So that said basically, this is how we can use Python to create this function, the knapsack without repetition. So see you in the next video.
22. Knapsack Without Repetition : All right, so in this video we're going to discuss the knapsack without repetition problem. Now, this specific problem won't work with this method that we created here for the unlimited amount or the unlimited quantity of items that we have. So we're going to use a 2D array and we'll talk about it in a second. But before we're going to use the exact same problem or exercise this example. So remember that with the, without version, we got 57 as the final answer. We're going to use the exact same example. And we'll see if we're going to get this and 57 as a result. So to do that, let me just delete all of these and delete these also alongside this. Now we can start, what we're going to do is to create a 2D array. So let me just create it and see you in a bit. As we know, this is the list or the array that we're going to create and can think about these as the weight. Since we need a weight of 10, what we're going to do actually is to pull up these empty places by some values. Regarding, are, considering that we have, for example, this tube. So there's two SD wait, let me just write them here. As we said earlier. We already have, for example, this two. And it has the value or the amount of 11. We have three with 18, we have four with 20, and five with 28. So let me just try them here real quick. So here we have the amount. We have 11, 18, and 20, and 28. So what we're going to do here, so let me just, alright. So the first thing we're going to think about in this problem is that we're going to fill these empty places by assuming that we only have this item to fill. So for example here, if we want to fill the weight of 0 with this item, we can't, so we'll just leave it empty with 0. Now again, if we have a weight of one and we only have this item. Now we can look at the weight of this item which is two, which is greater than one, then we can't do with actually. Now then we ask ourselves, if we have a weight of two, you have an item that has a weight of two. Can we audit? And we store it here? Yes, we can. So just going to store its value, which is 11. All right, so let me change the color to green and let me just delete all of these, write them again with the green. So as we said, here we have 0, 0, and here we can fit this too. So we're going to fit it. It's 11. Now, as you can see, we're going to ask ourselves if we have a weight of three and we only have an item of width two, can we store it? Yes, we can. So organic store 11 here. And it's the same for all of these, we're going to ask ourselves the same question. So if you have a weight of 10, for example, and we only have an item that has a weight of two. Can we store it? Yes, we cancel. We're going to store its value. Then we're gonna move on to this. Now here we're not just looking for this weight of three, looking for both 32. So what we're going to do is to write 000. And here we're not going to store zeros. Because remember we're going to have these two items together. So it's either we can store two or three or both at the same time. Now since we only have this as a weight of two, we're going to store this item which is 11. Then what we're going to do is to go to three. Now we're going to ask ourselves, can we store this right here? Yes, because it is equal to a. So what we're going to do go all the way back three times here. So we are the 11, we're going to go 1, 2, and 3 gonna go to this one which is 0. And here we have 18. So we're gonna check with 18 plus 0 is greater than this one. Then we're going to add it. In this case it is. So I'm going to add 18 him. So think about it that way. So you can either store to or you can store three. In this case, if you want to start, you can just store it with a value of 11. So we're going to add here 11. However, if you don't, you need to store the value of 18. Now remember that whenever we're working with this 2D array, if we want to have answers or if we want to make sure that we have a weight of three left in here, we need to go back three times as we did in the 1D array in the example of the width repetition problem. So in this case, what we're going to do is to go to all the way up and we're going to check three times before. And this case, if you are at this point right here, we can always add a width of three and end up with this row right here. So we're good. We are at here. We're going to get 0 plus 80 and we're going to have 18 as an answer. Now let's move on to this for now, we're going to ask ourselves. All right, So who have 11 or we have 18 plus this four minus one. So we're going to get 4 minus 3, which is 1. We're going to get to this point which is 0. So we're going to store 18. Okay? So 0 plus 18 equal to 18 is greater than 11. We're going to store it. Then we're going to move on to this file. Now, we're going to ask ourselves, is five greater than three? Yes, it is. So we can start three. What we're going to do is to go left, lets us think about it at first and r hat. So if we have a weight of five, we can surely store both items with which are 23. All right, so we're going to add these to them, 11 plus 18, it is going to be 29. Now let's think about it. The way we're dealing with this problem is that if we are at five, we're gonna just subtract three from it, so it's 2. We're going to go all the way to two, going to look at the value here, and it is 11. So we're going to either store this 11, just going to add it here, or we're going to take 11 plus 80, which is 29, and 11 plus 80 meters 29, which is bigger. Then we're going to start at 29. Now we're going to do the same exact thing for this one. So it is either 11 plus 18 or 11, so it would surely pick 29. So 29, all the way to the end. Now we're going to do the exact same thing here. We're going to ask ourselves, here we can store anything. However, since we have already 11 here, we're going to add it. And we're going to get to this point where we have four. We're going to check is this 20 plus the 4 minus 4. We're going to go all the way back to 0. So 0 plus 20 is greater than 18. Yes, it is. So we're going to store 20, then we're going to move on 20. We're going to also check is 20 plus 5 minus 4, which is at one. So here we have this 0 is 20 plus 0. There's not. So I'm just going to store 29 instead. So what we're saying here is that we don't really need this for if we want to. If you only have a width of five, we can store 32 and they will give us a better answer of 29 instead of having just this fall with an answer of 20. Now, if we think about this six, we can actually solve 24 with a value of 31. Let's think about it with the formula. So we are adhere at six, going to take six minus four, which is two, you're going to look at 211 plus 20, 31 greater than 9029. So we're going to store it right here all the way now, we're going to think about it with the seven. So at seven, we can store 20 plus the 7 minus 4, which is 3. We have 18, so 20 plus 1838. So we can either store 38 or the value above, which is 29, going to choose 38. And we actually used all of them all the way. Here where we have nine. Now let's think about it. If we have 20 plus nine minus four, which is actually five. So we're going to take 29 plus 20, which is 49. So we can either choose 49 or 29 will show you choose 2049, which is picker. And finally, for the 10, we're going to have the same exact 49 as before. Now as for this one, we're going to have the same exact values all the way till the file. Now we're going to check is 28 greater than 29? No, it doesn't. So we're going to simply store 2009. Now, when I said that if it's 28 is greater than 29, you can, you need to do 28 plus this. Five minus five, gonna go all the way to 0. We're going to look at the one above, which is here 0. So 0 plus 28 is greater than 29. No, So we're going to store 29. Now in this case at six, we are also going to store only 31 since there's nothing here at also 0. I'm sorry, right here. Then we're going to look at the seven. So here we have 38 and the value of this one That's Check it out. We have 28 plus seven minus five, which is at two. So 28 plus 11, it is actually 39, which is greater than 38. So we're gonna go with 39. Finally, we're going to do, for these last few ones, we are at 8. We're going to take either 38 or 28 plus 8 minus 5, which is 29. So 28 plus 29 is going to give us 46. We're going to choose it then 9 minus 5, which is 4. So we have at Fall 20 or 20 plus 28 or 49. So we have 48 or 49, we're going to go with 49, which is bigger. Then finally, for the last one, we're going to check if we're going to take 49 or we're going to take 8 plus 10 minus 5, which is at five also. So we have 29 plus 28, which is actually 57. And this is the greatest or the largest sensors that we can have. And as we can see, we got this exact same result as we did using our 1000. And this case what we did, we actually, we used the five plus two plus three. And if we wanna make sure in this example, can always do that by simply saying that you are here at this 57. How did you get it? You just added 28, which is the weight five into the ten minus five, which was here, This 29. All right? And this 29 means that you didn't add 4, you just add the one above which is at three, right? So here we have five till now. And now we're going to check is 29 and 11 the same? No, This means that you added 32 also. So that's it basically for the walk-through example of this problem. The next video we're going to discuss or work with the pseudocode that we're going to use and the code implementation. So see you.
23. Knapsack Without Repetition Pseudo-Code : Alright, so what we come to do now is that we're going to go through the pseudocode of this problem. Now that we have implemented or worked out with a solution and work through to this problem through an example, we can actually come up with the formulas that we are going to use in order to write out the pseudocode. So the first thing we're gonna do is to create our array or our 2D matrix. Now in this case, we're going to assume is that at first here we have an empty list. So what we're going to say is that the first one would be emptied. The second one will be having this item. The third one, which is here, will be having this item alongside this item also, the fourth row would be having these three items and the last one would be having all of these items. And when I'm say that they'd be having these items, I mean that they can choose wherever they want from these items. So that's it. Basically we start with an empty array. Of course we're going to fill it with zeros. And of course, the first one here is going to be all zeros also. So that's it basically. Now what we're going to do is to create our actual 2D matrix, which is a and then an image, MA. Now what we're going to do is to specify the sizes. Remember that we need an empty one here. So what we're going to do is to add one to it. So instead of having the length of four, for example, let's assume this example. We have 2345. So we have the length of four that we're going to do is to create this 2D matrix as a length or a size of five instead of four, since we need to add this empty right here. So what we're going to do is to say that the sizes should be n plus one for the rows and W plus one for the column, indicating that we need 11 columns here, all the way till the dance that we need to extract. Now what we're going to do is to start with our two for loops. The first one will be starting from, so I will be from 0 all the way to end. And this is inclusive. Then we're going to create another for loop. I'm going to name it. W is going to be from 0 all the way till the large W. And also this one is inclusive. Now what we're going to do is to check if we are at a specific position where we have I equal to 0. So if the rho I is equal to 0 or the column is equal to 0. So I could be 0 or w equal to 0. What we're going to do is to set this to 0. As we said, we have these values, zeros right here, and these will be used later. So whenever we want to get back to the previous position. So imagine that we are at this 1112 and we're asking for the previous position of this and it doesn't exist. Thus, we need to have something before an order for us to not have an error while I'm writing our code. So this is why we assumed this empty at first, which will be just zeros. So if I go to 0 or w equal to 0, what we're going to do is to say that I'm at I and w should be equal to 0. So this is the first condition. Now, the second condition, if the weights that we have while going through these weights are smaller than or equal to the actual way that could pass it through. Now, in this case, what we're going to do is to update the MA or this 2D matrix. So let's think about it for a second. Let's assume that we are at this position four, and we are at this right here. We have temp three. So we don't know this value yet. So we're going to check. The first thing we're going to check is that while passing through this, so if this three is less than or equal to four, now this is the case, it's true, then we can update it. How can we update it? We can either go by 4 minus 3, which will be one, and add to it this value of three, which is going to be 18 plus 0. Or we're going to take the value above it, which is 11. So this is why we need to check if the weights are actually less than or equal to this form. And of course, if this isn't the case, what we're going to do is to just take the value from above. And of course, one of the example of this might be is that we are at this weight three. I'm going to check if this weight is less than or equal to two and it's not less than or equal to two. What we're going to do is to simply take the value from above. So we're going to access the same an a at the same weight. However, we are going to access it with an index minus1 to have the value from the above. So that's it basically let me just take all of these and make them a bit smaller. And I'm going to write them here. Then let's continue with our code. So we said that if f equal to 0 or w equal to 0, we're going to do this. Now. The second condition is to check if the weights at the specific weight is less than or equal to the weight that we have here. And if this is the case, we need to update the actual 2D matrix. So what we're going to do is to check if this weight, so weight at a specific index, I'm going to leave it empty for now, is less than or equal to w if this condition is satisfied. But we're going to do is to update this specific i w to be equal to either, So the maximum between two things. So it's either the K i, so I'm going to write it here. So it's either at I minus 1 w. So it's either the value above or the value of the list. So we are at this 2D matrix, we're going to, as we said, we're going to roll back by one. And as for the columns, we're going to from w. So this, Let's suppose that we are at this value four and we are at this three weight. And I do four minus three, which is equal to one. So we're gonna do w, which is four minus the weights at a specific index that we're dealing with. And then what we're going to do is to add this value from values. So we're going to add the value of our new weight. That is, for example, this one, 18 or 20, or 28 or so on. So it's the maximum between the one above or the one from here. So that's basically this is the formula that we're going to use. Now we have, still have the last condition. So if these two conditions are satisfied, the last one is to just take the value from above. And as we said, this is not greater. I'm sorry, it's not less than or equal to our weight. We're just going to copy the value from above. So else, what we're going to do is to specify that the index at i, w, I'm sorry, the value of a should be equal to the value at I minus 1 w. So that's it basically for our pseudocode for this problem. In the next videos, we're going to implement them in our code or in our languages. So see you.
24. Knapsack Without Repetition Java Implementation: Alright, so in this video we're going to implement our function using Java. So the first thing I'm gonna do is to initialize our function that is a public static. And so can I return the integer? I'm going enablement knapsack. And it's going to take some parameters such as the wait. And I take an array of weight, then we're going to take deep values as an array also. And finally, you, I'm going to take the capacity or the length of these values and weights. Now what we're going to do is to, at first and she lies and w. Then we're going to build our 2D matrix, which is going to be called an a. And it is going to have n plus one and W plus one as the size of length n. So recall that we said that we need n plus one because we created an empty array or empty list here. And each time we're going to go through, for example, if you are at this and next, it's going to have an empty list plus this one. Or if you are at, hey, we're going to have this one plus this one, and so on and so forth. So this is why we added n plus 1 here indicating that we have and plus one grows. Okay, so now what we're going to do is to start with our for loop. So the first one we said that it's going to be called I all the way. And the second one will be j, so forth. Sorry, W. So w is equal to 0, then w less than or equal to, create a w. So w is less than or equal to capital W and W plus button. Then we can check if i o w is equal to 0. We're going to simply ignoring but by storing at I and w the value of 0. Now the second case is that if the weight at i minus1, and we'll see why it is I minus 1 is less than or equal to w. If this is the case, then we're going to update this one and do the maximum between two things. That is, the first one should be the actual value that we have. So I'm a at w and this p-value above it. Or what we're going to do is to go above. And as for the W, we're going to add w minus the weights at I minus 1. So that's it. Basically, this is how we can do it. Of course, we need to add a, something that is the value or the value of the items that we have. And we're going to see it in a bit. But for now, I'll simply add values at I minus 1. So let's think about it for a minute. What are we saying here? So we're saying that if the weights at I minus 1 is less than or equal to w. Now, let's refer to this by minus one. Why are we using I minus1 set of AI? Now, recall that we added here an empty list. So if a value, for example, if we are dealing with this one, it will have an index of one. However, in the list that we're going to get, we're going to have them as 2345. So let's suppose they are like this. So 2345 and their values or amounts are as follows. A 11182028. So these are the indices. So we have index 0, 1, 2, and 3. So if you want to access them from here, here we have the weights and here we have the values. And of course, if we want to store them in the list, we're going to need to sort on. For example, let's suppose that we are here at I. If we want to access this one, we are now at index one. However, this index is at 0 and this list of weights, because we added this empty list, which took up one place. So if we want to access these weights and values using I and w, we need to recall or remember this empty list. So this is why we are going to access them using the by minus one. So that's it. Basically this is why we use I minus1 here, here, and also here when we access the values at I minus 1. So this is how we can change it. And we still have the last condition, which is if these two conditions are not satisfied with just done a return are. Place the same value as above into it. And that's it basically. Now whenever we finish this while loop, we're just going to return the value at and, and capital W. So that's it basically for this problem. Now let's go ahead and try it out right here. So what I'm going to do is to create a main function where I'm going to have a value. So let's suppose we allocate values as a list. I'm going to have a divided 2345. Then I'm going to have weights. I'm sorry, I just come up. So here we have the weights. And the values should be as follows, 11182028. And of course, we're going to need the w, which is ten. And then we're going to have n, which is values dot length. So that's it basically now we still have to call the knapsack. So I'm going to return it into results of knapsack problem with, alongside these, all of these. Now what I'm going to do it is to simply print it out right here. So I'm going to print the result. Now if I go ahead and run it right here, and I'm going to get as the value 57, which is actually the same value that we got from this one. It is right here, 57 using this example and using our upbringing with where we've got 57 also using three plus two plus five. So that's it basically for this problem. If you want to see these two, the array, you can simply create it or return it right there, I'm sorry. So we can simply return it right here in a 2D array. And instead of returning this specific, one, can just remove this and return here this 2D array as followed. And of course, actually that what we're going to do is to store them in a result. Then we can go into a for loop starting with the result, that length. And we're going to add result at by the length. Then we're going to simply print them out. So result. And then add j plus some space, and then print some line r1. And we're going to get this 2D array. And of course, if we check this one that we built right here, it looks exactly the same. So we have 000 all the way to 11, then we have 001111, and then 929, 000, 011, 820, 29, 31, and then thirty eight thirty eight, forty nine. Forty nine. So it's correct. And the ending up with 46, 4957, and we have them right here. So this is the exact 2D array that we've got manually. So our solution is correct, and this is the proper way to implement this problem using Java. Sell the problem knapsack without repetition. So that's it basically for this video. See you in the next one.
25. Knapsack Without Repetition JavaScript Implementation: Okay, So in this video we're going to implement our function for the problem of knapsack without repetition using JavaScript. So the first thing I'm gonna do is to create our function, which is knapsack. And it's going to take the following parameters. So the W, the weight, the actual weight values. And then we can open it up. Now what we're going to do is to define both these indices that we're going to use. Then we're going to create our functional or the 2D array. And in this case it will be an array and plus one, as we said. Then we can start with our for loop. So I will be equal to 0, as we said, it will go all the way till the end. And then I'm gonna dated, then we're going to have p w. In this case, w is equal to 0, then all the way till the capital W and updated. Now each time we enter this loop, but we're going to do is to create a new array at a specific index of I. So it will be a new array of length w plus one to fill it. And now in this case, we're going to check if I is equal to 0 or w is equal to 0. What you're going to do is to simply add at this and I W a value of 0. Now the second condition is if the weights at a specific index and I'm going to denoted by I minus 1. We're going to talk about it in the bed, is less than or equal to w. This is the case. Then we need to update this W into one of two things. So the maximum between the value above it. So it is, am I minus 1 w? Or the second thing which is, as we said, we're going to go above and then go left by using w minus the weights at the specific index, so it is at I minus 1. And of course what we're going to do is to add the value to it. So the values at I minus one. And then this is what we're going to end up with. The last condition is at these two conditions are not satisfied, but we're going to do is to simply give this specific position, the value above it. So I minus 1 w. So that's it basically. Now let's talk about why we use the I minus 1 instead of I in this case. And the answer is that, remember that we use an empty array here. So an empty list criteria. And what we actually did is that we have the index of 0 for this, then we have the index of one for this, one, index of two for this, and so on and so forth. However, when we get the inputs, we're going to get them as follows. So to 11 has the value of the index of 0. And if you look at it at this case, we have it as an index of one and the 2D matrix. So what we're going to do if we want to access it, we're going to use I minus 1, which is 1 minus 1. We're going to have 0 and we can add set properly. The same, same thing applies for all of them. So if we are at index 2 right here, how can we access it using two minus one, which is index one. So that's it Basically this is why we used by minus1 here, here and there. So that's it basically for this problem, the last thing we're gonna do is to simply return the last one here, which is at and, and the large w. Now let's try it out. So I'm going to create values of 2345, I'm sorry. The weights. Then I'm going to have the values of 11182028. Then I'm going to have the weight of ten. And finally, at the end of that length, so values that length. And now we're going to call knapsack. So I'm gonna login it out knapsack. And alongside these, so w weights, then values, and then, okay, so now let's spend this problem or program. So what we're going to do is to navigate to this directory and we're going to call, Let me just call it right here. So node knapsack without repetition, ab.js going to run it and I'm gonna get 57 as defining value, which is the same that we got here. And of course here. So this is it, this is how we can solve it. Now, the last thing I'm gonna do is to visualize the whole 2D array. So instead of returning a specific integer, I'm going to return the whole array. Now, if I run it again and I'm going to get is an array and we have the first stroke, second, third, fourth, and 550. Now what we're going to do is to just compare them. So for stroke, actually all zeros, which is basically what we expected right here. Then we have 000 and then all of them are 11. Hey, we have the rest are 29, so we'll get correct. Then we have 3849 chart here. And finally we have 46, 4957. And here they are. So that's basically for this problem. This is how we can make sure that it is correct and our implementation of our code is actually correct. So that is it for the Knapsack without repetition using JavaScript. That being said, this is the end of this video. See you in the next one.
26. Knapsack Without Repetition Python Implementation: Okay, So in this video, we're gonna solve the knapsack without permutation problem using Python. So the first step that I'm going to take is to create a function and simply can name it knapsack. And it was big gong to take some parameters such as the weight, the weight values and n. So let's open it up. And the first thing we're gonna do is to create our 2D matrix. And this matrix should take two parameters. Now how can we build it using one line of code? We simply want to specify that for the row. So for x in range of W plus one. And then as for the columns, I'm sorry, this is for the columns and as for the row, I'm going to make it for range and plus1, as we said. Now, we can start with our for loop. So the first for loop should start in 0 and end with n plus 1. So for I in range and plus one, then the second for loop should start a range of 0 to W plus one. Sorry, we have capital W. And let's start with our code. So the first thing we're gonna do is to check if I is equal to 0 or w is equal to 0. This is the case. Then we'll simply want update or will simply going to add 0 into this value. So that's it basically now else. So what we're going to do is to check if the weights at I minus 1. We're going to talk about I minus1 Lebanon bit. But for now let's think about it as this. So if it is less than or equal to w, what we're going to do is to update the eye, the 2D array at the specific indices into the maximum between two things. The first one is the actual value that we have above it. So I minus1 as it is, I indicating the road and w or something else, that is the MA at I minus one. And as for the column, we said that we need to subtract from W, the waste that we're going to get. So this Pi minus one in this case. And of course we're going to add the value of it, which is at I minus one also. And finally, this is not the case. Also, we are going to do something else. That is to just take the value above it and add it to this one right here. So I'm at I minus one which is above it. So that's it basically now add score this I minus1 in the, wait. Why did we use it? Because if we go back to our pseudocode, as we can see, we said that we have an empty array here. And if we think about our weights and values, we have weights, values and their indices are as follows, 0123. However, in our 2D array, if you want to access this one, it is not at index 0, index1. Here we have the index 0, 1, 2, 3, 4, and 5. So if you want to access this, it is at index 2 here. However, it is at index one and our input. So this is why if we want to access this one, we simply subtract from one. So if we are at index 3, that suppose so we have 0, 1, 2, and 3, we are here. So at index 3, how to access this for using our empathy. So we make index 3 minus 1, which is 2. Now we can access it with using weights and values at index two. So this is the whole idea about the i1 x1 and how to use them. And of course, if you're confused with this, we can simply always add 0 here and here. So this will start at 0, and this will start at 1, 2, 3. But for not being complex or not, make it complicated, I simply added i minus one instead of I. So this is at now what we're going to do is to simply return the MA at the actual AND, and w. So this is the last input. Now let's try it out. So the values here are actually, as we said, we have 11182028. Then we have the weights which are 2, 3, and 4, and 5. Then we have the W, the weight that we're going to need to equal to 10, and just the length of the values. Now, let's try it out. So I'm going to print the knapsack. In this case, I'm going to have w weights, then values, then. And now if we go ahead and head over to our CMD, what we're going to do is to run Python knapsack without repetition. I run it. And here we have then valid index. You have a narrow saying that 0 for x and gains of 0. Okay, so here we have, we don't have engaged off, it's just have engaged. Now let's try it again. This is a typo. We have a length, we forgot to add the n here equal to now I think we're good. Now magnetic again, we're gonna get this result of 57, as you can see here. So this indicates that we achieved our goal. Now what we're going to do is to visualize the whole 2D array. So instead of returning this last value, I'm just going to return all of the array. Now if I go ahead and try that again, I'm gonna get this as we said. So we will have the first row, second column. And of course, if you want to make sure that this is correct, what we don't do is to simply compare them to these. So the first row, as we said, should be all zeros. The second row is 0, 0, all the way till 11. And the third would be 000 011, 1818, and then all of them, 29, then we have 000 011, 1820, 29. Then we'll end up with 49 and 49. And the last row will end up with forty six, forty nine, and fifty seven. If we look at it, we have 46 4957. So this indicates that our solution is correct. So that's it basically for this video. See you in the next one.
27. Number Of Subsets that Add Up to A Specific Number: Hello and welcome back. In this video, we're going to discuss the problem of finding the number of subsets that can add up to a specific number. Now in this example we have a set of four numbers, 1345, and we have the number nine, which we will use right now. So what we're going to do is to check if we have a subset or more than one subset that can add up to nine. And in this example, we have two subsets. The first one is 135, and the second is for N5. And both of them add up to 90. If you add up all of the elements indices inside the subset, and you will get nine as a finite value. Now, let's think about it for a second. The first approach that we can do is to have it all solved using recursion. And the reason I'm saying that is because if you want to think about it or we solve it by using a piece of paper. So for example, let's think about it. If we have an empty set right here. So let me draw it right here. What we're going to do is to get through each element and include it one time and get rid of it the other. So for example, At first we have an empty set. We're going to check if this is equal to 9. It's not. What you're going to do is to add this one from here. So let me change the color. We're going to add this number 5200 at one time. And we're going to just keep it as it is for the second time. Now what we're going to do is to check also have this is equal to 9. It's not. What we're going to do is to go to the other number, which is four. We're going to add it one time. And just keep five, the other term. And here we're going to add it and keep it empty. Now, we can move on to the third number, which is the 3. And works we're going to do is the exact same thing. So here we have 5, 4, 3, and here we have I'm sorry. Yeah. All right. So 54. And of course we're going to have here 53 and we're going to keep it five, right here, and so on and so forth until getting all of the possible combinations that we can get. And of course, we're going to check at each time we have built a screen, we're going to check if this is equal four. 29 for example, or this is equal to nine. So we have 54 is equal to nine. So then I increment the counter. So maybe you have a variable counter or something, and this will be incremented. So we have nine for now. Then we're going to check, for example, the other solution which is 1, 3, and 5, it includes five, is here, five, 53. And we're going to have a 531, which is also going to be true. And we're going to include or increment the counter. And as we can see to build this q, we need to use recursion or it's the most logical way to do so. Now what we're going to do is write the pseudocode for this recursion method. Then we're going to try and optimize it using dynamic programming or memorization. So let's go ahead and do it right here. All right, so a function will take three parameters. The first one is the list that we're going to have. So I just name it list. Then we're going to take a total. I'm going to explain it in a second. And then finally, an index I. So let's think about it for a second. What are we going to do? At first, we're going to build this array which is empty or less, which is empty. And then we're going to add 52 at one time and we're going to keep it as it is for this. And how are we going to do that? Let me just put it right here. So let me delete this and let's continue. So what we're going to have is an index that is pointing out at this number five. The first time we starting, then what we're going to do is to add this file, for example, to the list. Then after that, what we're going to do, we're going to move back one by one until looping through all of the elements. And let's suppose we add this element, which is four. So let me just denoted in red. So let's suppose here what we're going to do is to check if we can build a list or built this number nine using this list, only the elements that includes four and before. So what we're going to do is to check or create a function that get us this exact number, how many sets that we can do and that you can have two in order for us to get this number nine using just these elements. So if the index is add these three right here, we have the list of 13 only. So we want include 45. So this is what we are meaning by I going to decrement it. And. Check how many lists we can have an order to have this number nine. Now regarding the total, but we don't want to do is to decremented each time by the number at the specific index. And you can understand in a second once we sat with the code writing. And what we're aiming to do is to finally get the number of the possible such that we can have an order to get this number nine. So let me just delete this. And let's start with our code walkthrough. And we're going to talk and explain it while going through it. So the first thing I'm gonna do is, so this is our function. So let me just denote these parameters as this. And what we're going to do is to check once we reach a total of 0, this means that we consumed all of this number. We have a total of 0, then it is okay. We can return one. Since this is like a base case. For example, here, if we get to the total of 0, which is five plus four, is equal to nine, then the total of this will stay or will be 0 in this case, since we're gonna decrement nine by five, then decremented by four, we're going to get a total here, which is equal to 0. What we're going to do is to just stop right here and increment our function. So let me just name it recursion. So name it recur. And in this case, if the total is equal to 0, this means that we were able to get to a subset that add up to nine. And this case, what we're going to do to simply return one. Now, let's think about if the total is less than 0 in this case, such as this example, or maybe this one right here. Alright, So we didn't treat any point where the total is less than 0 other than this one. So maybe we'll just take this 5 plus 4, which is equal to nine plus three, which is equal to 12. And this case, if the total is less than 0, then what we're going to do is to simply return 0. So if the total is less than 0, we cannot return 0. Now keep in mind, we want, actually get to this point. We might get to a point where the total is less than 0 and other cases where 54 aren't subset of a possible subset. So for example, maybe we have another, maybe sex right here and we got 6 plus 5. Plus 6 plus 5 is actually 11 and this is greater than four, greater than nine, I'm sorry. So in this case, we're going to return 0. So that's it. This is for the second base case. Now let's move on to the third base case, which is if we got to a point where we reached the minimum index in have the index is less than 0, I less than 0. What we're going to do is to simply also returns 0, indicating that we reached the leftmost of our array. And in this case we didn't find any subset that can add up to nine. So if I is less than 0, simply return 0. So this is it for the base cases. Now we can start with our recursion function. So what I'm going to do is to just place them right here. And this one also, I'm going to place them as his heir. And now let's move on to the second or The fun part right here. That is the recursion actually. So now what we're going to do is to check as I will, total is less than a specific number. So for example, if we are at this number four, all right, so what we're going to do is to check if the total that we have left, which is nine minus five, which is four, is less than this number. Now, if this is the case, then we can't add four. However, four is not less than four, it is actually equal. So we can include a trend here. So we have two cases. The first one is if this number is less than four, so n is less than the number that we have in total. So let me just write it and then explain it further. So if the total number that we have left is less than the actual number inside this list, so is less than the list at a specific index I. And this is the case. This means that we can add up our, we can add this number 4 to our list or our subset. So what we're going to do is to simply move the arrow into the other elements. How do you do that? We simply return the same function. So. Recursion at the list. The same total since we didn't use this total and I minus1 indicating that we don't need this for anymore. Now, if this is not the case, what we're going to do is to return two things. First thing is that we add this for the second is that we don't add it as we said here. So for example, if you are at this specific moment where we have five and then we got to the index which is at this element for what we're going to do is at first added and then just keep the list as it is. And what we're going to do is to get the possible subsets from this part of the tree and all of the possible subsets from this positive k. And then add them, add them up and get all of the possible subsets. In this case, we have here one. So we have one here and we have one here. What we're going to do is to add one plus one and this will take two. And then we're going to return to as the possible quality final value that we have. So how do we do that? We're going to take to recursion functions and add them together. The first one is that we include this four and the second is just we give the list as it is. So what we're going to do is I'm sorry, we can just say else. But we're going to do is to return two things. That is the recursion at this list. The first time we are going to include it, we're just going to decremented from the total. So we're going to decrement list at i and just also decrement our counter. So what you're going to do is to include it and then go to this three right here. And we're going to do the exact same thing to all of the elements right here. So this is the first one and we're going to add it up to the same recursion. However, this time we're gonna keep the list add is, how would we do that? We simply return total instead of decremented by this element. So we're going to give five, which is nine minus one, total will stay for, and this case, we're gonna also decremented. So that's basically this is our formula. Now if you think about it, what we're saying is that we're going to go through all of this list from right to left. And then we're going to check if any of the base cases apply. If this is the case, we're going to return appropriate according number. So if the total is equal to 0, such as this case, what we're going to return is one. Otherwise you cannot return 0. Now for the recursion, recursion part, but we're going to do is to check if our total is less than the total here, the element right here. So suppose that we have a total of three and we have the number four. So there's no way that we can add anything to form that can make up to this total three because three is less than four. So what we're going to do is to simply move this index or this arrow into the one before it. So this is what we did here. And if this is not the case, if we can just put this for our set. But we're going to do is to add two things and to each other. The first one that is doing actually included in our set, and the second one is to actually just keep the set as it is. And then we're going to see the actual numbers from here and here and add them up. We're going to get the final number using this method recursion. So that's it basically for this problem. Now what we're going to do in the next video is to try to optimize it using dynamic programming and memorization. So see you then.
28. Improved Number Of Subsets Solution: Alright, so in this video we're going to try and optimize our solution for this. Finding the number of subsets that can adapt to a specific number problem. So the main drawback of our recursive solution is that we're going to call the same recursive, recursive function over and over again. And why is that? Because think about it. If we are at the specific number, for example, here at just five, what we're going to do is to call it one more time for 54, then call it one more time, 45403. So what we're basically doing is that we're going to add this four here. Then we're going to add it here. And then of course we're going to add it each and every time we go through this one, for example, this three, we are going to be called here, here. And then we have these left-hand Dr. Chris. And in this case it's going to be called over and over again. So what we're going to do is to store these values inside maybe a list, a hashmap dictionary, anything that we can solve it with. And what we're going to do is at each time we're going to run this function or call it, we're going to check if this specific parameter or these specific parameters are actually included in the list. So if this is the case, then we already included them and we already computed the number of subsets. And in this case we don't really need to go over it again. So one way to do that is, so for example, if we are here and we added five, then we added for the invaded three. In this case, when we add these three right here, what we're going to do is to add it to the list, for example. And then each time we call this 3, for example, right here, if this is actually the three was in the list, then we already computed It's number of subsets, then we don't really need to compute it again. And this is, this will allow us to actually save a lot of time. Because for example, if we are adding, for example, if you are here and we are ready, we find out that we already did this one. What we're going to do is to simply ignored the rest of the tree that is right here. So to start with it, first of all, we need to define a new parameter inside our function, that is the actual HashMap or the list that we're going to use. In this case, I'll just simply name it right here and name it as memorization. So I name it memo. So what we're going to do is to create a key and a value and store them inside this memo. So it will be either a dictionary or a HashMap that includes a key and a value. So what we're going to do is to store the key as the total and the index subtotal. And are we going to figure out a way to sort them in the key? And the value should be the number of subsets that we can have a given this specific number. So let's suppose we add at this one. What we're going to do is to store a key for this. And of course we're going to store at the value, for example, which is 0 for this because We didn't really get this and nine from the subset. So to do that, what we're going to start with is to construct our memo at the specific point. So if we call this function, we're going to do is to construct the key at first. And the key, what I'm going to use as a string. So I'm going to use a string. Plus I'm going to store the total comma, the eye, which is the index. So in the schema should be as the, so for example, what we're going to have inside this key is a. Suppose we are at this point which is here, what we're going to get is nine minus five, so the total is four. So we're going to store four, come up and the index is 0, 1 to the index is two. So this is our key. And our value should be actually the number of subsets that we can do tell this given point. And how can we computed? And it will go all the way back at this number, specific number one. And then this is how recursion works. So what we're going to do is to check at first, if this key is actually inside our memo, then we already computed. So we don't really need to go over it, so we simply return it. So to do that, we're going to simply add here if the key, so let me just make this a little bit smaller. And what we're going to do is to check if the key is an memo. But we're going to do is to simply return the value inside the scheme, inside the memo. So return memo at specific key that we created. Now, if this is not the case, then we continue, we're going to continue our recursive function. However, what we're going to do here is instead of returning them right away, we're going to just store them in a value and I'll name it to return. So we're going to store them in a two return, which is a simple variable. And then before returning them, we're going to store them inside the memo. So how do we do that? We continue writing the code here. So we're going to store at this memo, at key. We're going to store what we got, so we're going to store it to return. And then after that, we can simply return. So return to return. So that's basically now what we actually did is that we build up a key. Then we check if our value or what we are aiming to do is actually already in the memo. If this is the case, then we simply return it. That this is not the case, we're going to compute it. And then of course, added to our memo that before returning it back again. So that's it. Basically, this is what you need to do. And this will save us a lot more time and it will decrease the complexity a lot because we didn't, we aren't really calling the same function over and over again. Now, as for the actual runtime for this problem, Let's think about it. So for all these base cases, the actual runtime is O of one. So we don't really care about them. As for this specific one, here we have the functions we were calling one here and we're coming to write him. So it's either this one or two. Now we're going to take we're going to assume that we're going to meet Stan. So what we're going to do is to check how many calls are we making? And the actual solution? Or the answer is pretty simple because we're using this memo, so not calling a lot. So let's think about it. But we actually calling is that each time we decrementing by list I, I'm sorry, each time we're decrementing by I minus one. And in this case, we're going to call it the number. It says total times the actual number of items in this list. So why did we do that? So let's think about it this way. The number of potential causes that we come to do is related to the total and n. Because remember that we have a list as opposed tenses. This is the index 0 and all the way to 0123. So what we're going to do is to have the key and value according to this. So the key is actually what we did here, which is the total plus the eye. So it's fair to assume that we have n times for the eye because Annual Great, I would range from 0 to three. So we have four and the total will actually be, if, let's suppose that we have nine, it will actually be nine times four possibilities that we can get this key value pair. And in this case, this is total times n. And we're going to assume the worst case where we're going to call it twice. So we're gonna multiply it by two. And this is our runtime that is four. Now, we can always remove this constant and we're gonna get 0 of total times. And so that's basically for this problem. Now in the next videos we're going to implement them were in the languages that we have to see you.
29. Number Of Subsets Java Implementation: All right, so in this video we're going to implement our function using Java. So the first thing I'm going to do is to create a function with the four parameters that we talked about. So I'm just going to name it as we said. Or in this case, maybe you can change it into memos. All right, So I'll keep it for now. So public, static. And this should return an integer and it will be recur. And the Parliament parameters are the list that we have, the total, the eye and the memo. And of course, our list should be in an ArrayList or less. I'm gonna go with, I'm sorry, either an array list or an array. I'm going to go with an array list. So array list. And it will be of type integer in this case. Then there's our list. The total should be a number, the end, also a number to an integer. And finally here we have the hash map in this case. And it will take a key and a value. So alkene will be a string and the actual value will be an integer. So that's it basically now we can start with our code. What we're going to do at first is to check, as we said, we're going to build up the key and check if this actual memories and our Unless called demo. So how do you do that? We simply cannot construct the key at first. So let me just get rid of this. Returns 0. And we've got, what you're going to do is to construct the key strengths of strength k equal to string of the total plus the comma plus the actual number I, which has the index. Now, this key is actually is inside our memo. We're going to return it ever written its value from our memo. And how do we check it? We are going to use the memo that contains key method. And in this case, if it is true, we're going to simply return the memo at the specific key. And I'm sorry, we need to memo that. Get the specific gate. Now, this is not the case. What we're going to do is to check if the total is equal to 0. And this case, what we're going to do is to simply return 0. So we're going to check if total is equal to 0. I'm sorry, we need to return one indicating that we found a list or a subset that can adapt to the specific number. Now if the total is less than 0, but we don't have to do is to simply return 0, indicating that we didn't find any amount or any less that can add up to nine. It's bigger than nine. Now, the index I is less than 0 will also return 0. And finally, we can start with our recursion functions or recursion cause. And the first one is to check if the total is less than this list at a specific index which is i. If this is the case, then we can't include it. We're going to simply jump about by an index. And how do we do that? We're going to store it in a variable. So let me start by creating this variable here. So it is an integer to return and it will be initialized to zeros first. Now what we're going to do is to assign, to return into this recursive function. And it will take the following parameters. The first one is the list total, and then I minus 10, and then memo. And finally, once we're going to do is to check or it's the last condition. So we don't really need to check which then are added to the return. So return, it should be one of two things. It's either the list with the specific number on the list without it. So with total I minus1 memo plus recursion list with total minus the less at the specific eye. And then we're gonna do the same I minus 1 and memo. Now before returning this to return from here or here, what we're going to do is to store it inside our memo. So how do you do that? We're going to write memos. And then we're going to put inside this memo, this key, and the value is actually to return. Now finally, we can simply return our return integer, which is the number of subsets, but you can use. So that's it basically for this function. Now what we're going to do is to build up the cold, the main function where we're going to call, called this one and get our result. So how do we do that? I'm simply going to create a main function. I'm sorry. So let's create again. And inside our main function, what we're going to do is to create a HashMap. And it will take a string and an integer, and this will be our memo to be equal to new HashMap. Now what we're going to do is to create our list that includes the example that we did. So I'm going to write array list, and this will be add an integer. And then we're gonna name it lists, which is equal to a new array list. And I'm going to add a few things. So list that. I'm going to add the same exact numbers here to check if we get the same exact result. So 1345. So I'm simply gonna add 1345. Then what we're going to do is to have our total. So to be an integer called total, to be equal to the total that we need to choose that basically nine. And finally what we, finally, when I have as the index that we're going to start with, which is i, it will be equal to the list, that size minus one. So that's basically for our parameters now we can call our recursive function and print it out. So and simply print it out directly. So recur at a specific list, total I and memo. And then after that we're gonna run our code. And let's see what we are going to get for an alkaloid. And we're gonna get two as the final value or the final number of subsets that we can use in order to specific number that is 9. So that's basically for the memoization, which is actually recursion without repetition. As we can see, we did use the exact same logic of recursion. However, we didn't really need to compute each and every time we need a specific value, we can store them inside an array and then of course, get back to them later when we need to use them. And this will save, save us a lot of time, and it will decrease the complexity a lot. So that's it basically for this called walkthrough. See you in the next video.
30. Number Of Subsets JavaScript Implementation: All right, so in this video we're going to implement a function using JavaScript. So let's start with defining our function. So I'm going to name it recur, as we said. It will take a list and then you have the total, we have the index and the mammal that we're going to use. Now let's open it up. And the first thing I'm gonna do is to actually create our key. And this will be a string. So I'm simply going to add total loss, this comma plus I. Now what we're going to do is to check if this key is inside our memo. So how would you do that? We can simply use the function. If this memo that has the specific key, this is the case, then what we're going to do is to simply return the memo at this specific case. So how do we do that? We're going to take memo that get at the specific key. And then we're going to do is to simply continue with our code. So as we have the recursive function, inside this one, we have the total which is equal to 0. So if total is equal to 0, then we simply can't ignore it and simply return one as the return value. Because this means that we got to a point where we found out that we have a subset that returns a total of 0, which accomplished our goal in the first place. So in this case we are going to return 0. Else, if total is less than 0, this means that within a shape it will return 0. And then what we're going to do is to check if I is less than 0, then it also returns 0. Now we can start with our recursive functions. So if the total is less than this list at a specific index I. In this case, what we're going to do is to simply return the function recur as we said, and disregard, we'll have total I minus1 and memo. And there isn't a reason I minus1 is, as we said before, we're going to simply jump. Because if for example we have the list at i which is equal to 4, and we have the total which is equal to two. And in this case, total is less than this value right here. So we can really put this value into the subset. So we're going to just ignore it. So this is the reason now what we're going to do is to simply return a defining stage, recur at less total I minus1 memo plus the recursion add less total minus B. List at i minus1 lamps are at I. And then we're going to decrement it I minus1 and mammal. Now, what, what there isn't that we did this right here is because we're going to return the last two times. The first one is we include the 5. For example, if you are at five, if we include the four and the second one, if we don't include it. So this is what we're going to do. We're going to simply return the total hazardous. This means that we didn't include the four, and this means that we included the four right here. So that's it basically now what we're going to do is to change this into a variable. So instead of typing to return, I'm going to name a variable right here to return and it will be equal to 0. Then in this case, to return should be equal to this function. And of course we're going to do the exact same thing here. It should be equal to this. And finally, before returning to this variable, I'm going to store it in Zion inside this memo, going to use memo that said, and I'm going to set it at this kid gonna set the return variable and then I'm going to just return it back. So basically for this function now what we're going to do is to simply try it out. So I'm going to have a list of 1345 and we have a total of nine. And we have the I, which is equal to three in this case. And then we have our memo with jazz and new map. So memory map, and we're good. So these are all variables, so let me just place one bar. And we're good. This is variable also. Now what we're going to do is to call this function. I'm going to have the variable result. Note that for me, call this function with these parameters, so the total and memory. And finally, I'm going to just log it out. So console log the results that we have. Now if we go here and type node number of ways that JS, who can I get to as defined by the number of ways that we can have in order to reach this nine or the specific value that we have. So this is it for the implementation of the number of ways using memoization and JavaScript. See you in the next video.
31. Number Of Subsets Python Implementation: All right, so in this video we're going to implement our function using Python. So the first thing I'm gonna do is to create our function and name it. Prepare. As we said, we'll take the following parameters. The first one is the list. Then we're going to have the actual total deep index and the memo which will be the HashMap that we use or the dictionary in this case. So the first thing I'm going to do is to actually create the key that we're going to use. That is the total comma index. So how do we do that? I'm going to simply name it a key. And I'm going to simply write STR of the total plus become a plus index I. So STR acti. And then what we're going to do is to check if this is in the dictionary. If this is a memo, so F key and memo, that case. Then what we're going to do is to simply return the memo at the specific iso return memo, the specific key and we're done with it. This is not the case. What we're going to do is to simply check for the other base cases. So the first base case, if we actually succeeded and got to the point where the total is equal to 0, we're going to return one because we got away where we have a subset that can add up to the specific number. Now if total is less than 0, then we didn't get to a point where we have a subset which add up to 0, then we're going to return 0. Otherwise, we can also, we also need to check for AI, it's less than 0. Then we're going to return also 0, indicating then we fail to find a subset in this branch of this tree that we're building. Now, we can start with our recursive function. Functions. And the first one is to check if the total is less than the index of the value that at the end except we add, if this is the case, then what we're going to do is to return a recursive function without the specific index. So recall that if we are, for example, at four and our total is two, in this case score is greater than 2 says that this means that we can't add this four into our subset in order to have that the total that we are aiming to have. In this case, what we're going to do is to simply return this less total I minus 1 with our memo. So how do you do that? We simply let me just actually create a variable right here. And this variable should be just initialized by 0. And then we're going to add to return which will be equal to the recursive functions that we're using list daughter I, minus1 and mammals. Then if this is not the case, then this will leave us with two. Because of course the first one is to leave the list as it is, just decrement the index by one. And the other is to just take the list and decrement the total by the list at the specific. I am sorry, I forgot to either t Now I minus1 and mammals. So what we're saying here actually is that we're going to just use this for one time and just ignore it the second time. And this is what we are actually doing here, for example, here we're going to add this four to the subset. And he will not going to add it with simply going to return the subset or call it back without before. And we'll see one. It's common on later. So that's the basically for our function. Now finally, what we need to actually do is to just add it to our memo. So memo at this gauge is equal to return. And then finally our return. Now let's try it out. What I'm going to do is to create our list, which is exactly the same thing we built here, 1345. So list at 1345, then we're going to have a total of nine. And we're also going to have the index which is a three. It's going to start at the last element, which has been extra three. Then we're going to have the memo, which is basically a dictionary. Now we can call our function, I'm going to store it in a result and call it result, which is going to be a recursion less total and mammal, then you can simply print them out. So now if we go ahead and head over to CMD, go to desktop. And then by dynamic programming. And then I'm going to simply run this code python number of ways that by I'm going to get a messy. So we have an invalid syntax error. And this is actually because we forgot to add the column here and to end them criteria. So now if we go back and return number of ways, sorry, so here we have ads. So that's it. Now we can go back run and we got two as the number of ways that we can have subsets too that can add up to the specific number nine. So that's the basically for this implementation of this problem using Python to see you in the next video.
32. Longest Common Subsequence: Hello and welcome back. In this video we're going to discuss the problem of the longest common subsequence in S2 strength. So what we're going to have actually is to strength and we just write them down there. So we're going to have x, y, z, w. And then the other one will be x, the a w. Now, at the answer of this is actually the length of the longest common subsequence. In this case it is equal to three. How did we get it? We have x z w, x z, W. So as we can see, x, z and w is the longest common subsequence inside these two strings. And we might have some letters between them, but the order is the same, so we have ax than Z and W. So how do we solve this problem? Actually, our first thought we'd go into recursion since we need to find the possible ways or the possible combinations that we might have an each substring. And then we're going to check this substring matches the other end, the second string. And if the matches were going to find its length and then just return it as the a result. And of course we're going to find the maximum length that we can have inside these two strings. So how do you solve this problem using just the paper? What we're going to do is to check if the last two letters are equal. If this is the case, as you can see, W is equal to W, but we're going to do is to just remove them from our strengths and we're going to increment our counter by one. So here we have one. Alright, so now what we're left with is actually x, y, and z, and the first string and Ax and Ay and the other. Now if you want to compare the last two characters, we can see that they don't match. What we're going to do is to try it with two possible ways. The first way is to remove that dizzy and continue our solution using x, y and t firsthand and B x, z and a on the other hand. And then we're going to do the same thing. However, now we're going to get rid of a, so we're going to be left with x, y, z, and z. Now, if you follow this path, as you can see, we have x, y, z, and a. And this case, we're going to continue with either x and z and a, and the other solution should be x, y, and the x. So the first time we're going to remove the y and the other we're going to remove a. Now, remember is that we need to find a specific title that is at the end of these two strands and a should be equal. Now in this case, if we continue right here, we're going to end up with x and x on one end. And this case we found one that matches. So what we're going to do is to increment our counter here. And then of course if we continue, Hey, we're going to also end up with x and x. So now we have 11. What we're going to do actually is to check at this point, for example. So let's suppose that we are here. What we're going to do is to check the maximum between the left and right subtrees. And this case they are equal, so we're just going to return a 1. Now, we're going to do the same exact thing at this position. However, we didn't finish this branch yet. So let me just finish it. We're going to continue here. We have x, y, z, and z. They are equal. What we're going to do is to simply remove these dizzy from hay and increment the counter by one. And of course we're going to end up with x, y, and x on the first, and we're going to have x and x. And on the other hand, I'm sorry, let me just delete them. So we're going to have one time, x and x on the second time, than to have XY and nothing. And whenever we have nothing or an empty string, we'll just return 0 since we just went into a place that there is no such string or characters left. And one of the strengths, so we're just going to return 0, indicating that we didn't find anything until we have X and X. They are equal, so we should fit on one. So if we are at this position, x, y, and x, we're going to just take the maximum between these two strengths and it is actually equal to one. So here we have one. And if we are at this phase, X, Y, and Z, we're going to return the maximum between the one below it, which is actually just x, y and adds, and we're going to have one. So 1 plus 1 should equal, should be equal to two. And in this case we're going to return the maximum between these two branches. So you will have one and here we have two. So we're going to have to, and of course, we're going to end up with 2 plus 1, which is actually equal to three. So that's it. Basically, this is the tree that we can build. And what we're actually saying is that whenever we have two strengths that, that matches together. Two characters that are equal to each other. But we're going to do is to simply remove them and continue our work. However, we have two steps to do so. We either just remove busy or removed the a. And we're going to find out which is at the maximum substring or sub-sequence that can be returned using either x, y, z and a, or X, Y, Z and X, Z and the other case. And I will just going to return the maximum. And of course, whenever we have two string or two characters that matches, we're going to increment it by one. So that's it basically for this Just solution, recursive solution. And what we're going to do now is to actually write a pseudocode that helps us. And the next phase where we're going to optimize it. And we're going to find a solution using dynamic program. So before doing that, let me just think about the time complexity here. If we think about the possible combinations in a string and using statistics, what we're going to find out is that if you have a string of four letters, Let's say X, Y, Z, and W. So we're going to find the possible combinations that you might take from here. We can have either x, X, Y, XYZ, then we have y, y, z, y, w, and so on and so forth. And this case, what we're going to have is actually a combination of a few things. So for example, if you have a combination of just x, we're going to have a combination of one and c1. And then if you have two letters, X and Y are going to have and C2. And then NC3 all the way till b and c. And we're going to include all of the letters inside the string. So, and this is actually equal to two to the power n. And as you can see it, Exponential. Now, this is just to compute the possible combinations in one string. So we have two strengths. We need to multiply it by two. And then we're going to multiply it by n. And this n is because we have to compute the subsequence if it is common in the two strings. So we're going to find out if this is common, the two strands. So we're going to have from 0 all the way to n. And in this case, it is actually to the power n times n. So we can get rid of this two. So the time complexity is and two. And as you can see, and this quite large and have two long strings, we can really work with it and have a minimal time. So what you're going to do now is to write the pseudocode and then we're going to find a way to optimize the solution. So let me just get rid of these and I'm going to delete these also. Now what I'm going to do is to start with pseudocode. However, let me just take all of these and smaller, put them right here. So now we can start with pseudocode. What we're going to do actually is to start with the parameters. So I'm just going to name the function as longest common subsequence. And in this case it will take four parameters. The first one is Penguin, the second string 2, and then we have the position or the indices that we add. So whenever we say we're going to delete this or we're going to move to this one. We're going to take an index that just points out that this or this, or any specific character inside these two strands. So for s1 we're going to have ax and for us to have y. And the first thing we're going to start with is our base case. So the base case is actually where we're going to just undo and our function, and it will be actually whatever we have an empty string. So how do you find if you have an empty string? As we said, if x or y is equal to 0, such as this case where we have X, Y, and here we have an empty string. So the one which is indicating the position that we are in S2. So we are at position 0 or minus one in this case. And if we have the, we, if we are at this position, what we're going to do is to simply return 0. So fx equal to 0 or y equal to 0. We're just going to return 0. Now, we can start with our recursive calls. So we have two things that we should pay attention to. So f, the last character is equal. So if the last character S1 at x minus one and is equal to S2 at y minus 1. This is the case. Then we're just going to continue our work. Of course, we can increment our counter, which is the thing that we're going to return. So this should be actually written of integer. So we're going to return one. Plus we're going to call the function. However, we're just going to remove oil, decrement our counters by one. So if we are at this position, w and w just going to decrement it would be at z and a in this case. So how do we do that? We're just simply going to return longest common subsequence at S1, S2. As usual, however, we have x minus 1 and y minus 1. Now if this is also not the case, we have two things to choose between. We said that we need to compute the maximum between the left tree and the right tree. So how do we do that? Simply going to return the max between two things. That is the longest common subsequence. So longest common sub S1, S2 x minus 1 y. So the first one, we're just going to remove the first and last character and the first thing. And the second one, we're going to remove the last character in the second strength, so longest common subsequence. And in this case we're going to return S1, S2, and then we have x and y minus one. So let me just write them here. So we have S1, S2, and then we have x and y minus one in this case. So that's it basically for our recursive solution. And as we can see, it will take too much time since we are going to compute the same thing over and over again. So for example, here we're going to end up with x and x, and x and x, x and x. And of course you'll continue here. We're going to also end up with x and x. So we're going to compute it at least four times in this case. And as we can see, we're going to just compute a lot of things multiple times. So our second solution should be based on dynamic programming, and we can just get rid of computing these over and over again. So that's it basically for this problem using recursion. In the next video, we're just going to optimize it. So see you then.
33. Longest Common Subsequence Pseudo-Code: Okay, so now in this video we're going to discuss our dynamic programming implementation of the longest common subsequence problem. So we're actually going to use tabulation for this solution. So what we're going to do actually is to store our values are our results in a 2D array, and then use them each and every time we need to look at them. So let me just start by deleting the pseudocode of the past function. And we're actually going to do is to create a 2D array. And I'll explain why in a second. But this 2D array would actually contain our two strings. So as we said, we have x, y, z and w, and then Z and W. So here we have thrusts would just going to assume that we have an empty string. Then we have x, y, z, w. Then we're going to have empty string x, z, a, and W. So what we're going to do is to start by assuming that we have an empty string here and you have an empty string here. And we're going to just get the longest common subsequence. And in this case, the longest common subsequence is an empty string, which is length 0. Now, if we move on to the second place here, we have an empty string and acts that we can see. The longest common subsequence that you can have is actually of length 0 also. And here we have, we're going to continue with y and empty strings at the end of the string and W and empty string. And we're going to just fill it in with zeros and just compute the same thing here, empty string with all of these letters. So we're going to end up with zeros on both sides. Now we're going to continue, going to get to this point where we have ax and ax. And what we're actually going to do is to, if we have X and X, but we're going to do is to remove this x from here and from here as we did with this w. So if you have w and w, and we actually did is to remove the w's and then check for the x, y, z and accuracy. So the first time we're going to have this, for example. So if this is the case where we have X and X, then we're just going to remove this and check the one that doesn't contain the last character. So how do we do that? We're just going to check diagonally, because if we remove X from here and x from here, we're going to end up with empty and empty, which is here. So we're going to add one to the value from here, which is 0. So we're going to end up with one here. Now we're going to continue. We have x now and x, y in this case. So we are at this one, we're going to have x, y, and x. So the longest common subsequence is actually, according to our rule that we came up with before, is if we have two characters that don't match, in this case we have x, y, and Ax. What we're going to do is to check for a first of all, x and x. And then we have, So he will have x, y, and x. The first time we're going to remove the wire. And the second one time we're going to remove the xo. We have X and X and X, Y and empty string. So how did we just get this information? We're going to get them from the one before. So if we look at the one before, we're going to find out that we have X and X. And if we look up, we're gonna find out that we have x, y, and an empty string. So we're going to compute the maximum between these two according to our rule. So we have 10, the maximum is one, so we're going to fill it in with one. We're gonna do the exact same thing for XYZ and Ax, going to have one here and one here. So if you want to go over this x, y, z, and w. And so if you have x, y, z, and w and x, what we're going to get actually, because the last characters in these two strings don't match. We're going to continue with X, Y, Z, and X. And the other one should be x, y, z, w, and an empty string. And in this case, how do you look at them? We're going to look left and we're going to end up with XYZ and acts as we can see, this is it. So it's 1. And we also have x, y, z, and w, and an empty string which is actually 0. So the maximum between them is actually one. So just implementing our group and finding what we want from previous computations. Now we're going to continue with xy and x. In this case, what we're going to do is to look left and just above Soviet 0 or one, we're going to continue with one same thing here. We have 1 and 1, 1, 1. And of course here we have x z and x, y, z, in this case z and the matches. So what we're going to do is to add one into it and look at the one that is diagonal. In this case we have one and we're going to add one. So one plus one, we're just going to store two in this case instead of one. And if you look at it, the way that we were dealing with it before, if you have x, y, and z. And then we have x, z, but we actually did is to remove this z and z, we're going to end up with x, y, and x. We're just going to end up with also acts and deaths at the final stage where we have here one and here one, we're going to end up with two as a finite answer. So how do we do that? We simply look at the previous computations without computing x, y, and x. One more time, we're just going to take the value that we saw a. So it is 2. And of course we're going to end up here with all SO2. Now here we have 0 or 1, which is 1, 1 or 1, 2 also want one or two going to end up with 22 or two. Just going to end up with also. Now we're going to go all the way to the end. Now if we look at this, we have x, z, a, w x, y, z, and w. And in this case, as we can see, w and w that the same. So we just can add 12, the one diagonal, do it, which is two. So we're going to end up with three as a final value in this case. So what we actually did is that we used the recursive solution. However, we just store it our job, the results, in this case 2D array, and we just use them whenever we wanted. So instead of computing it, each and every time we want something, we're going to store it insists array. And as we can see, we can use it here or here, or here. So remember that we have two recursive calls. In the previous solution, we have the one if they match, and this case it is diagonal and we have the one if they don't match, we're going to take the maximum between this one or this one. So at first we're going to remove one element from this array or this string. And then we'll remove an element from this string and we're going to compute the maximum and return it to here. So basically for this problem now, what you're going to do is to implemented using pseudo-code. And then of course we're going to implement it in our languages. So do that, let me just delete this and minimize this one. And of course, what I'm going to do is to delete this. And I'm going to take all of this and place it right here. Now we can start with pseudocode. The first thing we're gonna do is to call a function. I'm going to name it longest. Common subsequence as usual. Now, we're going to have to ArrayList or array or a list. So I'm just going to compute them as just S1 is a list. Save that and stood as a list. And of course we're going to have the indices that we are at. In this case, I'll name it x and y. Now, the first thing we're going to do is to build our array 2D matrix and just named longest common subsequence, LTS. And it will be 2D. And of course what we're going to do is to assume that we have at zeros and empty strings. So the length of this should be of length or size x plus 1. So x plus one, y plus 1. Now we can start with our for loops. We're going to fill it this 2D array. And so we have the first one to go from 0 all the way to x, or the length of this. So it will be all the way till x plus 1. And then we have I plus 1, I plus, plus, so I from 0 to this. And then we have four j from 0 to y plus 1. Of course y plus 1, one is not included, or neither is x plus 1. And then we have j plus plus. And now we can start with M solution. So the first thing we're gonna do is if either i or j is equal to 0 is just going to fill them with zeros. I equal to 0 or j is equal to 0. What we're going to do is to fill the LCS i, j with 0. Then we're going to check if x at a specific position as equal. In this case, what we're going to do is to move back by one and then we're going to store the specific position. So how do you do that? Now, remember that we have S1 and S2 as a mate as a list. And this case what we're going to have as S1 as this x, y, z, and w. S2 should be of x, z, a and w. Now as you can see here, we have the index of this axis is 0. However, if you want to compute them in this 2D matrix, it is at index one. So here we have 0, 1, 2, 3, 4. So whenever we want to work with this, we should just decremented by one. So to do that, what we're going to do is to actually check if, let me just make this smaller a bit and just take off this also make it smaller. And now we can work. So the first thing we're gonna do is to check if else. This specific character that we are, ADH is actually equal to the specific character that we had and the second string. So if s1 at a specific x minus 1 is equal to S2 at a specific y minus 1. This is the case. What we're going to do is to fill at LCS x, y, I'm sorry, here we have I and j. So i and j. And of course here we have I and j. So if they are equal, we're going to do is to take the one. They are going to do it. So how do you do that? A I minus 1, j minus 1 and incremented by one. And there isn't that. We are assuming we are taking the condition at a swan I minus 1. J minus 1 is because actually our lists thought with the index 0. However, our 2D matrix we are computing at first for the empty string. So x here is at one and it is at 0 right here. So how do we do that? We simply take I minus1, which is if you are at this index I, which is equal to one, and just take this, we're going to take 0 minus 1, which is 1 minus 1. We're going to take 0 and we can get this X from the list as one. So we have j minus y and dy minus one. If this is the case, then we're just going to compute it from diagonal position. Now, if this is not the case, we're going to end up with the last thing we're gonna do is to compute the maximum between two things. The first one is the one at the left position and the second one is the one above it. So how do we do that? Who is just going to take and stored in the LCS i and j. So LCS, let me just write it here. I'm just going to move this here. And I'm going to write that SES at I and J equal to the maximum between two things. So the maximum between the LCS at I minus 1 and j as it is, or the maximum, or the second which is LCS at I and j minus 1. So that's basically for God, this is our dynamic programming solution. We just computed all of the possible implementations using just a 2D array. Now if we think about the time complexity, if we have m as, we have x and y as the length of S1 and S2, and we build up our 2D matrix. So as we can see, we have x, y, a time complexity of our code. And then our solution should be the last one and our 2D matrix, which is three in this case. So that's it basically for this problem. And the next video we're going to implement it using our languages. So see you then.
34. Longest Common Subsequence Java Implementation: All right, so in this video we are going to implement our function using Java. So the first thing I'm gonna do is to create the function. It should be public, static, integer. And I'm going to name it common subsequence, and it will take the following parameters. The first one is an array called S1. Then we have another is to have the indices x or x and y. So now what we're going to do is to create our 2D array and it will be of size and name it along. And in this case, the length should be x plus 1 and y plus 1. Now we can start with our for loops. So as we said, we're going to do is to go through all of these from 0 to x and from a 0 to y. So for an create a for loop. And in this case, to go all the way the act, yeah, who could have used the long content size or the length? And the second one would actually be all the way till y. Now what we're going to do is to check if I is equal to 0 or j equal to 0 would guess simply states that Islam should be at I and j should be equal to 0. In this case, we could have just ignored it because whenever we create a 2D array to the matrix or an array in Java, the default value is actually 0, so we can just ignore that, but we'll do as our pseudocode. So just keep it right here. Now, this is not the case. We're going to check if the S1 at I minus 1 is equal to S1 add j minus 1. So else, if S1 at I minus 1 is equal to the S2 at j minus one. If this is the case, what we're going to do is to place ads long I and j, the one diagonally to it. How do you do it? I minus 1, j minus 1. And then we're going to add to it a one. And of course, if this is not the case, still have the last condition, which is to check the maximum between the one on the left and the one on the above. So we're going to start at long-term I and j. The maximum at. So math.max, the lung at I minus one j and long-term at I j minus 1. So that's it. Basically this is our actual code. Now what we're going to do is to simply return the last value, which is at the X and W. So after finishing from this two for loops which simply going to return the lung, the x and y. Now, to try it out, I'm going to do is to create a main function where we're going to implement or so our variables then we're going to call the function. So we're going to have S1 to basically be equal to a list or an array of x. Then y, I'm sorry, I'm just going to put them as characters, so x, y, and then we have z and w. Z and w. Close it, and we have S2, which is also an array of X, Z and W. So x, z, and then we have a and w. Now we're good. We can continue with the actual x and y. So these are the indices that should be at. So this is the length which is four in this case. So both x and y equal to 4. Now I forgot to do is to print out the function. So I'm going to store the result, the actual function, and then of course going to print it out. So I'm going to print out the result. We have a typo, this is w. Now if we go ahead and run this code, what we're going to do to get a CI is three, indicating that this is the number of characters or the length of its sub-sequence that we have. Now to visualize it, what you're going to do is to simply print out each time we enter this loop. Then I print out our position. And of course I'm going to have space here and printed line here. Now if we go ahead and run this code, get the same exact result that we built right here. We have zeros, ones, twos, and the last one is actually three, indicating that this is our result right here. So that's it for this example. This is the implementation of this code using Java.
35. Longest Common Subsequence JavaScript Implementation: Okay, So in this video, we can implement our function using JavaScript. So the first thing I'm gonna do is to create the function. I'm going to emit longest common subsequence. And it will take the following parameters. So we have S1, S2, these are two lists and arrays. And we also have the indices and name them x and y. Now we can open up this function. And now what we're going to do here, we have a typo. So this is function. Now what we're going to do is to create our array. So I'll name it. Maybe. And in this case it could be a new array of size x plus 1. And of course we're going to have a new array inside each position and do it. I'll do it in a second. So our first for loop should be starting at I equal to 0, then all the way to x included and then incremented. Now the second for loop should be, should start at j equal to 0. J is less than or equal to y and increment j. And of course each and every time we get to a position of I, we're going to create a new array, y plus 1. Now what we're going to do is to check if I is equal to 0 or x is, I'm sorry, or j is equal to 0. So this is the case. What we're going to do is to simply store at I and j at the value of 0. Now, if this is not the case, what we're going to do is to check if at position S1 and S1, S2 J minus one. If they are equal, then we're gonna do some tensor as if disposition, which is S1 at I minus 1 is equal to S2 at J minus1. This is the case. What we're going to do is to increment i and j by one plus d value, which is at this position, I minus 1, j minus 1, which is the diagonal position of the specific value. Now as you're going to do, if this is not the case, we're going to take the maximum between two things. The first one is at the position which is at the left, and the second one which is at the above. So what we're going to do is to start at this specific position, which is I j. The maximum between the first one that is a long-term at I minus one and, and I'm sorry j. And then the long I and j minus 1, this case. Now this is our code. Finally, after finishing these two for loops, what you're going to do is to simply return the last value that we got, which is the long, come at x and y. Now if we go ahead and print it out, let me just start by creating lists of x, y. Then we're going to have z and w. Z. Then we have w. And we have list of, let me just name them variables. So we have variables. And in this case, the second one should be of x, y a, I'm sorry, x, z and a and W. So x, z, a and W. And now finally, what we're going to do is to have the indices which are at position 4 for now. So var x equals 4, y, which is also equal to four. Now what we're going to do is to simply call the function and lock it out. So I'm going to store it in the result. Come up and we're going to call it S1, S2, x, and y. And then finally, I'm going to log it out so that set. Now what we're going to do is to head over to our cmd. And of course we can add our desktop and JavaScript dynamic programming. This is so bad. And then of course we're gonna run our code using Node C dot js. If we run our code, we're going to get three as the final value that we got from this function. And this is the longest common subsequence that we can get. That is x, y, and w naught we're going to do is to visualize this function or this 2D matrix that we just created here. So instead of returning the last value, I'm going to return all of the 2D array, 2D matrix. And if we run it again, we're going to get the same exact result that we built by hand right here. As you can see, we have zeros, ones, and all the way till the last one, which is actually a three that said, for example, for this example, this is the implementation of this problem using JavaScript.
36. Longest Common Subsequence Python Implementation: All right, so in this video, we're going to do is to actually create the function using a Python. So I'm just going to create this file subsequence. And by now what we're going to do is to start with our definition or the function that we're gonna use, just going to image lung cancer and to take the following parameters. So we have S1, S2. You also have x and y as the parameters or the indices that we're going to use. Now the first thing I'm gonna do is to just create the longest common sub. And this will be the list that we're going to use. And to actually be a list of lists. And the first one should be for I in range of x plus 1. And then of course, the second unit will be in range of y plus 1. So that's it. Now what we're going to do is to start with our for loop. So to be in the range of 0 all the way till x plus one, since x plus 1 is not included. So this is the first one, as for the second would be ingrained of 0 all the way till y plus 1. Now what we're going to do is to check if i or j are equal to 0. If I is equal to 0 or j is equal to 0, this is the case. What we're going to do is to simply implement or add at this position, the specific position at I and j has a value of 0. Now, if this is not the case, we're going to check if at Aswan High minus 1 is equal to S2 minus S1. So S1 I minus 1 equal to S2 at j minus one. So if this is the case, what we're going to do is to simply take the diagonal value that we have and store it with incrementing one by itself. Longest common subsequence at I minus 1, j minus 1, and we're going to add one to it, and that's it. Now the last condition that we're going to have is that if these two conditions don't apply, we're just going to store the maximum between two things. The first one being at left. So it will be the maximum between the longest common subsequence, I minus1 and j, which is the vertical, so it's above. And the second one will be at I and then j minus 1. So that's it basically now, after finishing from digging this to the left or to the array, what you're going to do is to simply return the values at the specific indices. Now to try it out when you're going to do is to simply create the list. So we have x, y, then we have z and w. Then we have S2, which consists of x. We have z, then we have a, and then we have w. That's it basically now as for the ax equal to four, y equal to 4. Now we're going to print it out. We're going to print s1, S2, x, and y. So now let's check it out. I'm going to head over here and I'm gonna go to by dynamic programming. Five, sorry, so dynamic, sorry, we have any typos and we're going to do is just simply run the code. So now we're going to run it using Python and Python. So longest common subsequence dot py. So here we have an error. So I'm sorry, here we have set of using LCF, we have LF and Python. So LF, Python. So we also need to pay and what we actually did this, we call the function and print it out. So let me just store it, I'm sorry. And as a result, so I'm just going to place it and error results and then just call it or printed out after I'm done with computing the value of salt. Now, after that, what we're going to do is just simply go here and drag again. And as we can see, we got three, the final value, which is the longest common subsequence that we can get. Now instead of returning this whole list or the last element in the list, I'm going to return this 2D matrix. Now if you go back and refresh, and as you can see, we've got our function, our 2D matrix, and as we can see, it is the same exact unless that we've just built it by hand. So that's it basically for this problem, the last value is actually what we're interested in. So this is the implementation of this longest common subsequence function using Python. So see you in the next video.
37. Longest Increasing Subsequence : Hello and welcome back. In this video we're going to discuss the problem of the longest increasing sub-sequence. So the idea of this problem is that we are given a list of integers and we are going to return the length of the longest increasing sub-sequence. So for instance, if we have this list right here, we have 15, 7283, then what we're going to return is the number five, indicating the longest increasing sub-sequence in this case, that is O157 than eight and 10. So this is the longest common subsequence and we're going to return the length of it. Now, the first time I have when solving this kind of problem is usually recursion. Since we need to find the longest increasing sub-sequence, we may think about the idea of finding the longest increasing sub-sequence for each index. So for example, if we are at here, the longest increasing sub-sequence for this specific element is actually one. Now, here, what we're going to get is two, because we have 15. Then at seven, it's three, then a two. I'm back to two. Since we have 12 we can deal with. Then here at eight is going to be four. And then of course at three and it's going to be 1, 2, and 3, which is 3, and at ten it will be five. So this is basically the idea about this problem. Now what we're going to do is to check how we can implement it using recursion. So the first thing we're going to do is to build the CI that we're going to have. So remember that whenever we want to solve this problem, let's assume that we are at the specific position, which is at index number 0, 1, 2, 3, and 4. So we are at index four. How can we solve this for the specific climate? How can we know that the longest common subsequence for this element is actually four. So the first thing we're gonna do is to create the condition or the function for the index for. And what we're going to do actually is to check the maximum between all these before this specific index and then add to it one if it is greater than the actual numbers. So how do we do that? We're going to add one to the maximum between F3 and F2, F1 and 0. And of course, they should all be less than or equal to this specific element at a specific index. So this is a must, and of course, this is the function that we're going to do now remember that this is just for, uh, for, now if you want to compute f 0, F1, F2, and F3, we're gonna do the exact same thing here. So for example, we have this and then we have here will need to compute for F1 and F2. And as you can see, we're slowly building a tree where we're going to find just for this specific element of four, we're going to compute all of these and then compute them again and again and again. And of course we're going to do the same exact thing for all of these indices right here in our list. So as you can see, this will take an exponential approach and the runtime will be exponential. So let me just show you maybe the pseudocode of this. Jim. And of course we're going to try to optimize it using dynamic programming. So the first thing we're gonna do in this recursive approach is to build the function. So I'll just simply name it longest increasing and it will take the following parameters. I'm going to have the array or the lesson. I'm going to name it the list. And I'm going to have the integer and indicating the length of this list. Now what we don't want to do is to check the base case. Now, remember that we should return the maximum length. So maybe I can create a global variable outside. Maybe I'll name it Max length. And in this case, I'm going to update it inside our code right here. So what we're going to do is to check if you are at the base case, which is n equal to 0 or 1 in this case, what we're going to assume is that we're going to start with one. So we don't really need to compute 500. We're going to start with F1, F2, and so on. So a fan equal to 1 is equal to one we're going to do is to simply return one, since it's the first element in the list and we should return its length, which is basically equal to one. And if this is not the case, remember that we should compute all of these four. Specific index. So if we are at U4, we need to compute F3, F2, and F1. So in this case we need a for loop to do that. And for each one of them, we're going to check the return value. And if it is greater than the maximum that we already have, we should update our maximum. So how do we do that? We're going to simply just define two variables. Our result that we're going to get. And of course, the maximum, which is the current maximum. So I'll just name it Current Max. And now what we're going to do is to compute this. So how do we do that? We're going to call this function for this specific indices. So for, we're going to start with the eye all the way from one till the value of n. And of course we can increment it as we go through. Then what you're going to do is to get the results from this function. So we're going to store in the result the function of increasing with our list and the indices. Now, I'm sorry, the index is actually, now what we're going to do is to check if this list at the specific index I minus 1 and n minus one. If this is less than n minus one, then we should update it. So how do we do that? Let me just grab this and make it smaller. And let's look at it that way. Food are at this specific position where we need to compute this afford. What we're going to basically do is to go through all of these F1, F2, and F3. And we're going to check if the specific position is the element in this list is less than the element of afford. So for example, if we are at this F1 and let me assume that this is a fourth. So this is the index 4, 1234. And what we're going to do actually is to check if this specific position is less than this one. It is. Then what we're going to do is to check the maximum length in this case, which one is it? Less than the maximum length at this specific position, which is basically 0 at this case. And so if this is greater than this one, if it is, then we can take this incremented by one and put it right here, which is basically two. We're gonna do the exact same thing here when we compute this one. So the length here is two. Is it greater than or equal to 2? Yes, it is. Then we just take two plus one and incremented if this is the case. Now, as you can see, five is less than, I'm sorry, it is greater than two, then we can do that. So we have two steps or two conditions to be satisfied in order for us to update this current maximum. So let me just write them down. The first thing we're going to check if the list at the specific position, which is I minus one, because we're starting at one and these indices start with 012, 34, and so on. So if this list I minus 1 is less than the specific list at the end that we're dealing with. So n minus one, if this is the case and our result plus one. So we need to remember that if you are at the specific position, we just take the results from the end incremented by one and then check. So if this result is greater than the current maximum that we have, current max, then what we're going to do is to simply update the current max. So the current max would be, at this case, their result should be equal to the result plus 1. So that's the basically this is how we can update our current maximum. Now, after finishing from this whole for loop, which is of this. Alright, so let me just draw it. What we're going to do is to simply check if the current max that we just got in this case is greater than the maximum length of the total array or P total list. If this is the case, then we need to update this max length. So F total, I'm sorry, if current max is greater, then the maxlength. We need to update the slider. So max length should be equal to the current max. So this is at basically this is our whole code and code. Now, after finishing all of these, what we should return, this function actually is not the maxlength, is the current max. And the reason why is that? Because let me just take all these and make them a bit smaller. I'm sorry. So let me just do it from here. I'm going to take loop and just minimize it and place it right here as before. And there isn't that we're going to return this current max is because our function is about this current match. So remember, if we are at this four loop, what we're going to do is to take this current max from each and every one of these elements, so we should return the current max. However, when we need to call this function will not basically interested in this kind of math. We're interested in the updated version of the maxlength that we dealing with. So to say that basically for this pseudocode, and as you can see, this runs in an exponential way as we are computing this lung. Thank each and every time we ended this for loop and we're calling it so many times because it is a recursive. So that's basically for this video. In the next video we're going to try to optimize it using dynamic programming. So see you then.
38. Longest Increasing Subsequence Pseudo-Code 1: Okay, So in this video we're going to try to optimize our recursive function and using dynamic programming. So the thing is, whenever we're using recursion is we calling this function over and over again. For example, if we are at this specific position of ever for what we're basically doing is to code F1, F2, and F3. And in this case an F2, we're going to call F1 and F3 we're going to call F1 and F2 again. So instead of doing all of that, what we're going to do is to simply create a for loop that loops through all of these together. So F1 and F2 and F3 and checks the maximum between them. And after that, we're going to return it or just place it in this F4. And of course we're going to increment it by one. So instead of using this pseudocode where I'm going to do is to simply get rid of it and start again. So what we're going to start with is actually to build the function where we're going to have the list and the index. And so I'm just going to call it longest increasing SQL server. It will take a list and the integer. And now what we're going to do is to create a list where we're going to store the longest increasing sub-sequence up to the point of these indices. So for example, if you are at this specific position, which is index one, but we're going to store in the other list that we're going to create is the longest increasing sub-sequence to this case, which is actually two. All right, so let me do that here. This is our second list, so I'm going to name it L I, S, indicating that this is the longest increasing sub-sequence. And it will be of size. And in this case, as usual, now to go to do is to initialize our indices I and our maximum value. So we have I, J, and Max. And all of these should be initialized to 0, so maximum to be at 0. Now what we're going to do is to start with our for loop, Salem, the LINCS with one. Since in each index we have, for example, if we are at index two, the minimum number here is one. So the length of the minimum possible subsequence actually is one, and it just includes this number itself. So for example, if you are at this specific position five, the minimum length that we might have is actually one, which is at this five right here. So to do that, I'm going to afford look from all the way till n and simply store and LINCS at the specific position I, the value of one. Then what we're going to actually do is to create to an asset for loops, pass through all of these items or all of these elements inside this list. And then at each element. So let's suppose we are at this specific position, that is the specific position 3. But we're going to do is to pass through 012, get the maximum between these. And as long as the value inside these positions are less than the value at two and the maximum here are greater than this, then we can update it. So what we're going to do is let me just write it here, but before that, let me minimize this and then continue. So what we're going to say is that we're going to have a for loop of I till n. And then inside this for loop, we're going to start from 0 all the way till I. Of course, I should start at 0. Then what we're going to do is to check, as we said, if the list at this specific position I is greater than the list at, I'm sorry, here we have j from 0 all the way till ISO, j equal to 0 the way till i. And here we have I equal to 0 all the way till n and is less at I is greater than the list. So if we are, for example, at this right here and we have an equal to 3 that suppose what we're going to do is to look through all these elements from 0 to. And what we're going to do is to check if these items are less than the item that we have. Then if this is the case, what we're going to do. So we're going to end it with the longest increasing sub-sequence. So let's suppose we are at this specific position where we have one. We're going to take one and add to it one. So this will make two. And remember that we initialized all of these to one. So if you are the specific position which is at index three, and we're going to have one AD as the longest increasing sub-sequence. For now, we're going to take 1 plus 1, which is equal to two. We're going to check if two is greater than one. If this is the case, then we need to update this. So to do that, we're going to check at at a specific position, which is j plus 1 is greater than the LINCS at the position of I. If this is the case, then we need to update our LAS at atoi. So I'll IS at, i should be equal to S at j one. So that's it basically now we're going to have a list of these right here. So we're going to have 1, 2, 3, 2, 4, 3, and 5. And of course, to get the maximum, we're going to create another for loop that helps us get the maximum from this Elias list. So to do that, let me just make this here. And what we're going to do now is to create another for loop, looping through I equal to 0 all the way till the end. And we're going to find a maximum undistorted and the maximum variable right here. So if Elias at I is greater than maximum, we're going to store and maximum this value of Elias at I. So that's it basically now what we're going to return is to simply return the max that we just computed, which is actually the length of the longest increasing sub-sequence that we have writing. So we simply return max, and now we're good. So this is our function. Now, if we want to call it, we can simply just run it using the array or the less that we have and it's index or the size of it. So that's it basically now, thinking about the time complexity. Here, we use two nested for loops, starting from 0 all the way till n. And we also have from I equal j equal to 0 all the way till i, which is basically in the worst-case scenario, we're going to have n, So we have m squared right here. And what we actually did in the auxiliary space is that we sold them in an array or a list, and it will take a space of n. So the time complexity is O n square and the space complexity is O of n. So that's it basically for this problem. In the next video, we're going to implement it using our languages.
39. Longest Increasing Subsequence Java Implementation: Oh, hey, so in this video we're going to implement our function using Java. So the first thing I'm going to do is to create the function that we can use. So it is public static, and I'm going to name it the longest, increasing. And it will take the gray. And now what we going to do is to create the longest increasing sub-sequence, which will also be an array of size n, as we said. Then we're going to initialize our indices. And of course we're going to initialize the maximum which we're going to use. After that. The first thing we're going to do, as we said, is to fill in the list the longest increasing sub-sequence with ones. So we're going to start with I equal to 0. I is less than or equal to n, and we're going to increment it. Then what we're going to do is to fill in the longest increasing sub-sequence at the specific position I, the value of one. After that, we're going to continue with our for loop. So we have two nested for loops I less than n and I plus plus. Then we're going to continue with j equal to 0, j less than i, and implement j. As we said in our pseudocode, we're going to check if these values at list or the array at I is greater than the array at j. And we're going to check if the longest increasing sub-sequence at j plus one is greater than the longest increasing sub-sequence at I have. This is the case. We need to update the longest increasing sub-sequence at a specific position. So if array at I is greater than the array at j, and as we said, the longest increasing sub-sequence at j plus one is greater than the longest increasing sub-sequence at I have this is the case, then we need to update it. So longest increasing sub-sequence, I should be equal to the one at j plus one. So basically, this is how we can construct our array. Now, after pressure from these two nested for loops, we need to find the maximum and store it and the max value. So we're going to look through I equal to 0 less than n and then increment I. Then we're going to check if the maximum is less than the longest increasing sub-sequence at the specific position that this is the case, then we should update the maximum to be the value that we have right here. Now after that, but we're going to do is to simply return the maximum that we have. Now, let's try it out. What I'm going to do is to create a main function where I'm going to create the array that we want. Now. So the aeration be, let me use the same exact example. We have 15 728310, so 157283. And then we have the length n, which is basically the length, the length of this array, 1, 2, 3, 4, 5, 6, 7. So n equal to seven. Now and I'm going to do is to store the result in an integer called result. And I'm going to call this function, which is the longest increasing sequence. And of course, I'm going to print out the result as here, alpha, go ahead and run this code. I'm going to get five as the longest increasing sub-sequence. And if we go back here, you can find that our less consists of five elements indicating that the length of this list is actually five. So that's it basically now 400 go further into it and visualize this. I list the longest increasing sub-sequence which consists of 1232435. What I'm going to simply do is to return a list or an array instead of this. And I'm going to simply return here the longest increasing sub-sequence. Then what I'm going to do is to store it in a result such as this. And I'm going to create a for loop. And of course, I'm going to print it out as this some space. And if we go ahead and run this code again, we're going to get 1232435. Now. We need to just there. So we have 1232435 and as we can see, we have 1232435. So the results matches our expectations. And this is the documentation of the longest increasing sub-sequence using Java.
40. Longest Increasing Subsequence Javascript Implementation: How k. So in this video we're going to implement our function using JavaScript. So the first thing I'm going to do is to create our function and I'm going to name it. I'm gonna get a list and the integer and indicating the size of this list. Now what we're going to do is to create another list that is the longest increasing sub-sequence. I'm going to name it ally. And an array of and this is the size. And I were going to fill it with a 1s. So that's it basically. Now let us initialize the indices I and j. And then we're going to initialize a maximum that we're going to use, which will be equal to 0. Then we're going to start from I to 0. I'm sorry, from I equal to one till i equal to and, and just implemented. Then we're going to take J, which is equal to 0. So j from 0 to I, and of course we're going to increment it. Now we're going to do is the same thing as the pseudocode. We're going to check if the list at i is greater than the less than j. So if list at i greater than a, less than j, and we need to check if the Elias at j plus one is greater than DALYS at i. If this is the case, we need to update this alliance at I to be equal to Ls at j plus 1. Then after that, we can return the maximum. Now, what we're going to do is to search for the maximum inside the list. So we're going to start from 0 all the way till and, and updated. Then we're going to check if max is less than the Elias at the specific position we're going to update it into. So max should be Elias at I. And of course after that we should simply return the maximum. So that's it. This is it. This is the function that we're going to use now, I'm going to do is to create our list, so to run it, so let's just equal to the same exact list that we use. We have 15, 7283, and 10. So 157283 and 10. Then we have n which is equal to 7, basically. Then after that, I'm going to store the result in a variable called result. And two will be the longest, increasing as less than 10. After that, I'm going to log it out. So I'm going to log out results after that. What I'm going to do is to head over to the my directory, which is the JavaScript dynamic programming. And then I'm going to run this code using Node java script. I'm sorry, node. And the name of the file longest increasing sub-sequence dot js. And so we have an error here. So let's see, inside the module not found. So I think I wrote it wrong. The longest increasing sub-sequence. So it's increasing sub-sequence node learn increasing sub sequence that has no forensic and we're going to get five as the longest increasing sub-sequence that we have. And if you want to visualize actually this list of the longest increasing sub-sequence, which is 1, 2, 3, 2, 4, 3 and 5. We can simply return the Elias instead of the maximum here. And now if I go ahead and go back, read it again, I'm going to get 1232435 as the result that we expected and as the result that we actually generated by end here. So that's it basically for this problem is, is that for the longest increasing sub-sequence using JavaScript.
41. Longest Increasing Subsequence Python Implementation: Okay, So this is Python implementation of the longest increasing sub-sequence problem. So the first thing I'm going to do is to define the function. I'm going to name the longest increasing. And it will take the array or the list that we're going to have a simply named list. Then we're going to have the index n or the size of this list. What we're going to do actually is to store and a new list. I'm going to emit ally us. We're going to store once and they aren't going to be. And once. After that we can start with ranging or the two for loops. So for I in range from 1 n, We're going to go from j in range of 0 till i. And we're going to check, as we said before, inside of pseudocode, we can check if the list at i is greater than listed j. So let me write it down real quick. So less at I is greater than the list L, j. And we also have, sorry, and we're going to have the LINCS. J plus 1 is greater than the LAS I hat. J plus 1 is actually greater than the Elias at i f. This is the case. Then what we're going to do is to update the ALS at L2. I'll add j plus 1. After that, we can define the maximum that we're going to use. So the maximum should be at first 0. Then we're going to look through all of the Elias list, which has the longest increasing sub-sequence for each. And that's, and in this case for I in range of 0 all the way. And so I'm simply going to write, and if the maximum is equal, latter larger than the actual maximum variable that we have here, then we need to update this one here. So how do we do that? We can simply write the maximum is less than the LSAT. I will update the maximum to be at a specific position i. After that, what we're going to simply return as the maximum that we created right now. Now to check it out, what I'm going to do is to create a list, which is exactly the same thing that we, hey, So we have 15728310. So we're going to have inside this list 15, 7283, and 10. Then we're going to have n, which is equal to 7. After that, I'm going to store an a result, the longest increasing sub-sequence with less and n. And of course I'm going to print the result out. Now, check it out. What I'm going to do is to simply head over to CMD desktop and to Python dynamic programming directory. And I'm going to run this code. So longest increasing sub-sequence dot py. So here we have an error because we created a variable result and we can't use it in Python. So now if we go back and refresh, as you can see here, we're going to get five as the longest increasing sub-sequence inside this sub-sequence of integers. Now if we want to see the whole list, that is what, the 1, 2, 3, 2, 4, 3 and 5. We can simply just return back the maximum, just the ally as, as it is. Now if you go back and run it again, we're going to get this list 1, 2, 3, 2, 4, 3 and 5. So these are the actual longest increasing sub-sequence for each and every index inside our input list. So I didn't have 0 at the longest ingredients. Oblique muscle is one, index, one, it is 23. And here we have two because we, at the specific position, which is we are, we have to, the longest increasing sub-sequence is 12 and its length is actually 2. So that's it basically now what we actually did at the end is to compute the maximum of these, which is five, and return it as our result. So that's it basically for this problem. This is the implementation of the longest increasing sub-sequence using Python.
42. Project : Okay, So in the last problem, we solved the length of the longest increasing sub-sequence using a time complexity of O n square, as you can see here. So what we actually did is to find the length of the longest subsequence inside a list of integers such as this one, and it's the longest one is 15, 7, 8, 10, and its length is actually 5. Now what you suppose to do is to enhance the solution hour to find an improved way in terms of the time complexity. So our time complexity is O n squared. Your task is to improve it into o and login. So what you need to do is to think about a method and implemented using your favorite programming language and improve the solution in terms of time complexity. Now, keep in mind when dealing with such problem, you may sacrifice the space complexity to have a better time complexity. So for example, if we're not using an array or if we using a list, we can use more. You can use 2D matrix, a HashMap or anything of that sort in order to improve your time complexity. So we're just focusing on the time complexity and ignoring the space one for now. So that's it. This is your task. I hope you enjoy it. Score, and don't forget to drop your project in the project section. And good luck and enjoy.
43. Conclusion : So congrats, You just finished this course. This is just a quick recap about what we covered in it. So the first thing we did is to use Fibonacci sequence to define memorization and tabulation and learn the differences between them. Then we solve some of the most famous dynamic programming algorithms. And at first we draw the trees, their IRAs or 2D matrix alongside the pseudocode that we're going to use. After that we implemented them using our languages. So now, just quick tips. Whenever you sold this kind of dynamic programming problems, you need to solve it by a 100 thirsty tried to come up with the solution that works, maybe by recursion. And of course, after that, you can start by optimizing it and coming up with a better solution by either using memoization and tabulation. So with that being said, this is the end of our course. I hope you enjoyed it. Finally, if you have any questions or suggestions or improvements, then I can make the discourse. Or if you want me to cover extra problems, please ask it in the Q&A section. And it would be great to leave a review so I can improve this course. So thank you for being here and good luck on your next journey.