Transcripts
1. Introduction: So what is dynamic programming will simply stated, it's a programming methodology that focuses on breaking down the prompter given into many smaller but similar subproblems. And then through some clever optimization, allows you to solve those subproblems very quickly so that by the end, you have that final solution that you are looking for. And moreover, it can provide some dramatic improvement to your code in terms of both efficiency and speed. And also understanding this concept and knowing how to apply it to solve problems will be extremely beneficial in technical interviews for software engineering roles. And I currently work as a software engineer myself. And I can tell you from experience that in every single technical interview that I've gone through for the various companies have applied to in the past. At some point in the interview, I was asked to solve a problem by writing code on a white board where the solution to that problem required the use of dynamic programming. So if you have an interest in obviously computer programming or potentially pursuing a computer science degree in college or maybe a software engineering role thereafter. And this would be a great course for you to watch because I'm going to walk you through step-by-step. A couple example problems that you may encounter in an interview or on the job or in school. That of course, requires dynamic programming to solve the problem. And at this is the first course of mine that you've come across. My name is Scott race. As I said, I currently work as a software engineer in the financial services industry. And I have degrees from UC Berkeley in both computer science and economics. So that being said, let's get started.
2. What is Dynamic Programming?: All right, welcome to the first video of this course on dynamic programming. And in this first quick video here, just kinda giving you a brief introduction, obviously into what dynamic programming is. And so I just have pulled up here the basic definition from the geeks for geeks website. And so the main idea here is that dynamic programming is simply an optimization over plain old recursion. And just in case you don't know, recursion is just the concept that a function is going to call itself over and over and over again until it hits some sort of base case, at which point it stops were calling itself, and then it returns back up the stack until it ultimately finishes. And so, like I said, dynamic programming is simply an optimization on top of this. And the core idea is that we're going to store results of sub-problems so that we do not have to recompute them later when we might need them. And what that basically means is whenever you're given a problem that can be solved using dynamic programming, you're able to always take that problem and break it down into smaller subproblems and a very similar nature. And instead of trying to solve each one of these sub-problems independently, all by themselves. We're actually going to use these solutions of some of the sub-problems to very quickly solved other sub-problems. And so ultimately the way this works is, you know, of all these different sub-problems and they're all getting very similar nature. There's gonna be one though, that is the most basic in nature, and we call this the base case. And the base case subproblem is going to have a very easy intuitive, logical solution. But that's super simple solution can actually be used to very quickly solve another subproblem that might be a little bit more complex. And now the solution to that sub problem can then be used to solve another subproblem that might be even more complex. And it just slowly builds from there like a snowball effect. And it still sounds a bit confusing or abstract. Don't worry, you'll see a lot of really detailed examples in this course so that by the end, a very firm understanding of dynamic programming obviously, and then how to leverage it in interviews and potentially on the job. And the last thing I want to mention before I wrap this video up is because dynamic programming is an optimization over just plain old recursion. You can't see massive improvements in performance and efficiency with your applications. You know, for example, if you look down here, you can see these little code snippets for the Fibonacci number problem that I'm actually going to be walking you through in the next video. There are two ways to solve this problem. One, English just involves the plaintiff recursive method, and the other approach, of course, involves a dynamic programming. And you can see the runtime efficiencies of these two problems are quite different. With just plain old recursion, it's an exponential runtime, whereas with dynamic programming it's only linear. And so to put that in perspective, you know, if you have a very large input into one of these functions using a simple recursive method. It could take hours or even days for a function like this to actually compute the solution that you're looking for. Whereas with a dynamic programming approach, that same huge input could still only take a few seconds to process. And that's truly how different these two approaches can be in terms of the efficiency. And that's also why just knowing how to code, right? Just knowing how to, for example, write these little code snippets to make them technically work. It's likely not gonna be enough to get you a good software engineering job if that's what you're going for. And that's because the job of a software engineer is, of course to write code, but to do so in the most efficient manner as possible. And this concept applies to all engineers, whether you're a software engineer and mechanical engineer, electrical engineer doesn't matter. Their sole job is to solve problems in the most efficient possible manner. And so if you can really understand and master this concept and you understand how to use it when solving problems so that the runtime of your applications or your algorithms on the order of only a few seconds as opposed to, you know, hours or days depending on what the input sizes, that's going to be hugely beneficial for you in interviews and of course, on the job. I hope this gave you a pretty good high level introduction and understanding of what dynamic programming is. An next video coming up, we'll be diving into the Fibonacci numbers example a lot more so that you can see a real life scenario and real-life problem that you might be asked to solve in an interview. And this is supposed to be a more easy to understand dynamic programming question. And then as we get further in this course, the examples I'll be walking you through it will get increasingly more difficult. So see you the next one.
3. Fibonacci Numbers (Easy): Alright, welcome back. And in this video, as I said, we'll be diving into the Fibonacci Sequence problem that I kind of briefly talked about and showed you in the last video. And as you saw, there are two main ways to approach or solve this problem. The first of which involves just plain old recursion. And that method is going to be very slow and sluggish and inefficient. And then of course, the dynamic programming approach is just going to be an optimization on top of that, that's going to, as you will see, be a dramatic improvement in terms of speed and efficiency when trying to solve this problem. And so the code you're looking at here is just three simple functions written in the Go programming language. And if you'd never seen go before, don't worry, it's actually very easy just to kind of read through and understand what's going on. And syntactically speaking, it's actually quite similar to Java and C and that kinda thing. So hopefully it should be very easy to understand what's going on here. And I'll be walking you through it, of course. And so we have the main function that's going to be just the entry point of our application. And then, as you saw in the last video with those two little code snippets, I'm, I basically have them rewritten right here. And this is just the function that's going to perform these calculations just with the plain old recursive approach. That's why it's just called fib recursive. And then the second function down here is called fib Dp. And this is the dynamic programming approach that's going to solve this problem. Before I get into it, just in case you are actually unfamiliar with Fibonacci numbers and how this all works. It's simply a sequence of numbers that starts at one and goes on to infinity. And the basic structure of this sequence of numbers is basically each number is the sum of the previous two numbers. So for example, if we look at the number two here, and I should also mention the sequence itself just always starts with 11. And then from then on, every number is the sum of the previous two numbers. So looking at this two digit right here, this of course, is the sum of 11, the previous two digits, then going to three. This digit is the sum of 21. And then five of course, is the sum of 32 and so on and so forth. And that's really it. That's the entire concept of the Fibonacci numbers. And so the problem we're trying to solve is we want to write a function that's going to calculate the nth digit in the Fibonacci sequence. So for example, if I wanted to calculate the fifth digit in the Fibonacci numbers, that would be the number five, right? 12345. This is the fifth digit and it just also happens to be the number five. And so now let's focus on just the regular fib recursive function. The function that's just going to do this calculations with Planum recursion, No dynamic programming involved. And I'll walk you through this to show you why this approach is actually very inefficient. And so let me explain this code first through an example. So let's pretend I'm indeed looking for the fifth digit, now the Fibonacci numbers. And so when this function gets called by the main function, we're gonna pass in the number 52 are arguments here. So this n is just represents the nth digit we're looking for. And that's gonna be set to five initially. And then we hit, we hit this if statement of course, which as I referred to in the last video, this is our base case, and I'll explain more of that in a minute here. But just looking at the if statement, obviously five is not less than or equal to one. So we just skip this for now and come down to our return statement. This is where things get interesting because this function is now going to recursively call itself again two more times. One time with the argument of four, right? And minus one is four. And the second time with a value of three and minus two. And this should make sense because in order to calculate the fifth digit of the Fibonacci sequence, we need to first calculate the fourth, third digits so that we can actually add them together, which would bring us to that fifth digit. And so focusing on just this first function call right here with the value of four, right? This function is going to call itself and is now four. We hit the base case again. Obviously it doesn't really matter because four is not less than or equal to one. So boom, we're right back down here to the return statement. And once again, this function's going to recursively call itself two more times now with a value of 32, which again should make sense, right, to calculate the fourth digit, the Fibonacci numbers, we got to first calculate the third, second digit and add them together. And this process is just going to repeat itself over and over and over again until at some point the base case is actually true, right? At some point, N is going to be less than or equal to one. In which case we just return what n is and we don't make any more recursive calls. Alright, this is just the most basic form of the problem we're trying to solve. That's why it's called the base case. So for example, you know, when n is equal to one, that just corresponds to the first digit of the Fibonacci numbers, which we just know is equal to one. And if n is 0, then that doesn't really make any sense because nothing comes before the first digit, so we just return 0 in that case, right? So let me show you this now in a visual way. And this is where you'll actually be able to see why this approach is so inefficient. So this is just a little tree structure that shows you all the different recursive function calls that get made. And you can see in parentheses the arguments that get passed in. So of course we start at the top with our initial argument of five, right? In the.m, we're trying to calculate this fifth digit of the Fibonacci numbers. This function call ends up calling itself two more times with the arguments of 43. And each of those recursive calls, calls the same function again two more times with different arguments. In this case it's 32. And then it continues on from there and just exponentially calling itself more and more times until of course you get to the base cases which are down here, right? When we call the function with the values of one or 0, as you can see right here in the if statement, we just return and that point what n is. So that's where the recursion stops. And then we return back up the tree to ultimately calculate what the final solution should be, the fifth digit. But if you take a closer look, you'll see that we call the same function with the same arguments multiple times. For example, looking at this function call right here with the value of two, we call it here, and then we call it again here, and then we call it again here, right? So we are redundantly calculating the same exact thing three times when in reality it should just be calculated one time. We only ever need to calculate the second digit of the Fibonacci numbers exactly once so that we can use it to then calculate the third digit. And you'll see what actually calculating the third digit twice, right? More redundancy. And we're actually calculating the first digit, 12345 times. And in the base case, we'll rehab. The input is 0, that's here and here and here. So point being, we're doing a lot of redundant calculation, which, you know, if you can imagine if the input was not just five, but let's say 100. You could imagine how massive this tree we get an all the redundant calculations that would be involved that are just wasting CPU, wasting time. When in reality, like I said, you only ever need to calculate each number in the sequence exactly once. And that's where the dynamic programming approach is going to come in because that's what it's going to allow us to do. Only calculate each Number one time and then no more redundant calculation after the fact. But let me first actually show you how inefficient this code actually is. So I've already gone ahead and compile this code here. And right now the main method is just set to call and print out the result of just this simple fib recursive method right now. So I'll go over to my terminal here. And this is how I'm going to execute my code. This little dash n argument allows me to specify which nth digit I want the application to outputs. So just kinda going with our example here, I want to find out what the fifth digit is. So I'll go ahead and press enter and then boom, very quick. The answer is five, of course. So let's do something a bit more difficult or terms of processing and so on, that will do the tenth digit. This is going to be 55, again, very quick. But once you start to get a larger input size, right? As I said, maybe 100 or so. Now if I want to calculate the 100th digit in the Fibonacci numbers, I hit enter. And there you go. It's still processing. Still processing. No answer yet. And I honestly have no idea how long this could take. It might take ten minutes, it might take three hours. I honestly have no idea. I'm not going to sit here and wait for this to finish, but as I'm still talking, it's still not finishing. So I hope this has proved to you that, you know, the 100th digit really isn't that large of an input. And yet it's still taking a long time for this particular simple recursive approach to actually calculate the results. So I'm just gonna go ahead and control see it. So now, going into the dynamic programming portion of this, this is going to allow you to massively speed up the efficiency of that kind of calculation. And so this is where I want to tie in the idea or the concept of the sub problems that I was talking about in the last video. Write each of these sub-problems that we're trying to solve and then use the solutions of, are going to be the calculating of digits in the Fibonacci sequence that come before the digital we're actually looking for. So going with our example again, we really, really care about the fifth digit. That's our main problem. But the smaller subproblems are calculating the fourth digit and then the third digit, the second digit, the first digit. And so there you go. We basically have four other smaller subproblems that we have to calculate and figure out the answers are first, so that we can eventually get to the real problem that we want to figure out, which is the fifth digit, right? And of course, we want to find solutions to all these subproblems by calculating their solutions only exactly one time. And so the way we're gonna do this is we're going to start at the bottom right, calculating the first digit of the Fibonacci sequence, which is basically given. And we're going to in essence store the result of that calculation so that we can quickly use it to then figure out what the second digit is, store the result of that. And then we can quickly use that. Answer to solve the third digit than the fourth and then finally the fifth. And this is how we will only ever calculate the solutions to each of these smaller sub-problems exactly once. And so now let me come back to the code here. And so this is where I'm going to be walking you through this FIB DP method, which of course is the dynamic programming approach to solving this problem. And it's actually going to be very similar in terms of its structure to just the fib recursive method. Except there's gonna be a subtle difference of now we have this array argument and this is going to act as our memory component. That's why I called it men for short. This is going to hold the solutions of these smaller subproblems that we calculate along the way to getting to our final answer of the fifth digit. And so the way this is gonna work is, you know, for example, whenever we calculate the, the answer for the third digit in the Fibonacci numbers. The answer for that subproblem is going to be stored in the third index, the third spot in this array. And then likewise with the fourth digit in the Fibonacci numbers, that answers are gonna be stored in the fourth index and so on and so forth. And this allows us to, later on come back, look at the array c, if there's already a number or already a digit that's been calculated previously. And if so, we can simply take that number and use it instead of having to go down and do more recursion and recalculate that same number more than one time. So we still have the same base case here, although I wrote it a bit differently, I'm not sure why. So when N eventually gets down to either one or 0, we just return the value of what N is, right? If n is 0, we just return 0. If n is equal to one and we just return one. So same base case. So we basically just added this one extra little if statement that basically says, you know, we're gonna go into our array and we're gonna check to see if the answer for the nth digit is, has already been calculated before. And if it's, if it is, then we're just going to fetch it out of the array and return it. And just as a side note, this array, when it first gets passed into this function, all the indexes are initialized to 0. So 0 is basically the way we identify whether there actually has been a calculation done in the past or not. So if it is 0, then obviously we have to go down and do the recursion and figure out what the answer is for that nth digit. But if it's not equal to 0, then there you go. We've come across a solution for one of the subproblems that has already been calculated in the past. So we can just grab it and return it and just skip all the recursive nonsense that is completely unneeded. And of course, if none of these if statements hit, then this is where we actually have to go and calculate the nth digit of the Fibonacci sequence. And whenever this recursion returns and we finally get the answer, this is where we store it in that array so that somewhere further down the road, if we ever come to the point where we're trying to calculate the same digit. Again, there's no need. We already have it stored in the array. We can just fetch it out and return it. Coming back over here it is kinda see this visually. So the first time we calculate the second digit in the Fibonacci series, you know, we actually have to go and calculate it. So we do that recursion. We call the same function again with the values of 10. And those are just base case scenario. So. When these functions return though, we'd get our answer and then we store the value of the second digit into our array. So that next time later down the road, when we come to the point where we have to calculate the second digit, again, there's no need. At this point, we look into our array and we see, oh, we've already calculated the second digit before. I'm just going to fetch that out and return it back up. And then that eliminates the need to do anymore recursion and totally removes all the redundant calculation that you see in this tree. So now coming back to the code, I'm going to make a few tweaks here. I'm not going to comment out. The function call is just our normal fib recursive method. And then uncomment out the dynamic programming that Fib DP function, right? And memory here, this is where we initialize our little memory array and then we're gonna pass it into our FIB DP function call and then print out the result riots and they go ahead and save this code. I'll come back here and recompile it. Alright, so now let me go ahead and run this code with the same arguments that I didn't previously with just the normal recursive approach. So once again, calculating the fifth digit of the Fibonacci numbers and go ahead and press enter. And once again we get five as expected. Then they go ahead and do the tenth digit, Cat5 once again as expected. And now, when I do the 100th digit, as you recall previously, with just the normal recursive approach, it never finished right? Now I press enter, boom, instantaneous. It's pretty massive number and it was able to calculate this in a fraction of a second still. So right there, I hope this proof to you how drastic of a performance improvement you can get out of optimizing your code, whether that's through dynamic programing or something else. But point being, dynamic programming is truly a significant optimization over just a simple recursive method and can literally make your code run in just a fraction of a second, as opposed to minutes, hours, or even days depending on what the input argument sizes, right? So I hope this example, and there's kind of walk-through made sense to you. I do know that this dynamic programming concept can be a bit difficult to grasp, to understand at first, I know I certainly struggle with it in school when I was learning it. So I do recommend writing as functions out for yourself and really trying to think through how these functions are working. Maybe actually set some breakpoints and stepping through the code to see how things are executing step-by-step, so that you have a very good firm understanding of what's going on behind the, behind the scenes. So that when you are given more difficult problems to solve, you're able to still kind of navigate the issue and figured out what the subproblems are and how to develop a recursive approach that stores the answers to these sub-problems along the way so that you can drastically speed up the performance of your application or your algorithm. So with that being said, that wrap this video up and in the next one coming up, we'll be diving into a bit more of a difficult problem. I had referred to this as more of a medium difficulty problem that you might encounter in an interview or something. And it's can revolve around finding all the different unique paths from some start plays to some destination on checkers board or chessboard of sorts, given that there are certain barriers along the way. So pretty interesting problem. And of course it's going to be a great candidate for a dynamic programming approach. So thanks for watching, and I'll see in the next one.
4. Unique Paths (Medium): Alright, welcome back. And in this video I'll be walking you through another problem that's going to be a little bit more difficult in nature just in terms of trying to really understand and think your way through a possible solution to the problem. But you'll see later on that the actual solution itself encode is going to be very similar to the solution that you saw for the Fibonacci problem that in the previous video. So just diving right in here. The problem we're trying to solve in this case is going to be given some kind of, you know, checkers board or chessboard of sorts, right? And had little diagram shown right here that I'll walk you through in a minute. So given some kind of board like this, we want to find the number of unique paths from tau, s, That's our starting tile, to tile it, E, that's our end tile. Given that you can only move either down or to the right. And then tiles marked with an X are basically barriers and you cannot cross those. So coming to our little example right here, and this is the actual board set up that will be trying to solve for in this, in this video. So you can see right here, this is our starting tile and this is our N tile. And of course these little Xs are the barriers. And so once again, we're trying to find all the possible paths, at least the number of unique paths from S, two 0s. So as an example, one path might be from S and we go down, down, down, down, and then all the way to the right. And remember we can only move down or to the right, so that's one path. Another unique path might be down and then all the way to the right, down again, write down down. And so obviously there are many other more unique paths along the way. I believe there are 11 and total. And so you know, this is, like I said, this is the particular setup we're trying to solve in this video, but the algorithm we're going to write should be able to take in any kind of bored with any kind of dimension, right? This is a five by five board, but it could be a five by ten or an 11 by 223 by eight, and any sort of random assortment of barriers along the way. So really given any kind of bored, we should have an algorithm that should solve this problem, right? Calculate all the number or calculate the number of unique paths through that board from S to E. So now when trying to apply a dynamic programming approach to this, to this problem, the first thing you wanna do is try and figure out what the smaller but very similar subproblems would be that you can kind of solve along the way throughout the execution of your algorithm. And such that you can use the solutions to those subproblems to eventually calculate that final answer that you've been looking for. So I encourage you to pause this video for a minute and just think about a smaller but very similar sub-problem would be that would allow you to kind of build your way up to finally calculating that total number of unique paths from S to E. So go ahead and pause the video and come back when you're ready. Alright, I hope you took a few minutes to think about that. And so I'll just dive in to the solution here. And so in order to calculate the number of unique paths to this end tile, we first need to calculate the number of unique paths to the adjacent tiles, basically that one. And this one right here, given that, we can only move either down or to the right. So from this tile we can move to the right to get to our ETL or n tile. And from this tile we can move down to get to our end tiles. So as I said, we first have to know the number of unique paths to these tiles from our start tile. But in order to calculate the number of unique paths to those tiles, we need to first calculate the number of unique paths to their adjacent tiles. So that would be this one and this one. And so I hope you can start seeing a pattern here in that, you know, in order to calculate the answer to our, our real problem that we're trying to solve. We need to calculate the number of unique paths to all of these empty tiles, back to our starting tile. And specifically, the number of unique paths to our end tile is going to be the sum of the number of unique paths to its adjacent tiles. So if there's maybe, you know, five paths from start to this particular tire right here. And then there are six paths from start to this tile. Then summing those two together, that's going to be 11. And so that some 11 is going to be the answer to this entire, alright, there's going to be 11 total paths from start to end. And that's how it's gonna work for all these tiles, right? The number of unique paths to this tile, for example, is going to be the sum of the number of unique paths to its adjacent tiles. So and keeping in mind, of course, that we can only either move down or to the right. So for this particular tile and the only way we can get to it is moving down from above. Because of course we can't come from the right since this is a barrier right here. And so the number of unique paths to this particular tile is just going to be the number of unique paths to this tile, right? The way you can basically think of this is, you know, let's say there are two paths from start to this tile. And there are obviously 0 paths from start to as barrier tiles. So the total number of unique paths to this guy right here is just going to be the sum of two plus 0 basically. And that just equals two. And just as one more example, looking at this tile right here, the number of unique paths is going to be the sum of its adjacent tiles, right? And now both the adjacent tiles are open. So, you know, if there are three paths to this tile from our start, and there are maybe four paths from start to this tile and the sum three plus 47. And there's gonna be seven unique paths to this tau right here. And so we can build a very simple recursive function that would do this. But if we're not using dynamic programming in the sense of we are basically saving or storing the results of all these tiles along the way, then the runtime of this algorithm is going to be extremely inefficient. And that's because, you know, Let's say for example, we're looking at this empty tower i here, and we are trying to find the number of unique paths from start to this empty tower right here. So we basically would have to traverse the entire board looking at all the possible roots back to our start tile. And whatever number that is, we would have that on hand and then we would do it again from this tile, right? So again, we would traverse the entire board all over again and figure out the number of unique paths from start to this tile. And then once we have that answer, we can obviously just sum those two together and we get our final solution. But that's very inefficient because going back to this tile first, once we navigate the entire board and figure out all the possible paths from One to r start tile. Then when we do the same thing again from this tile, there's gonna be a lot of overlap, meaning some of the paths from this tile back to our start tile are going to overlap with the same exact paths from this tile. D2 are start tile. And so as an example, let's say one of the paths that we figure out from this tile back to our start tile is we go this way and then work our way back this way, this way. Boom, bone back to our start towel, right? That's the path that we take. And so when we do the same thing from this tile, at some point we're going to try and figure out a path that goes along this route. And then boom right here. This is where the two paths would intersect and we would take the same exact route back to our start point. And so by computing this path all over again, that's just a waste of time. If we get to this tile at some point and we already know there is a way back to our start towel from this point, then we should just stop there and use that information, right? If for example, let's say we're trying to calculate the number of unique paths from start to this adjacent tile right here. When we're doing that, if we eventually find out there are, let's say, three total unique paths from this tie right here back to our start tile. Then later on when we're trying to figure out the number of unique paths from start to this adjacent tile. Whenever we come back as we're trying to traverse our board again, whenever we come back to this tile again, we should just know that, okay, well, in a previous calculation, we've already figured out there are three unique paths back to our start point from here. So I can just take the information and use it and not have to recompute any further. And so this is where this men board is gonna come into play. Man is short for memory again. And it's basically just an exact duplicate in terms of the dimensions of our board right here. And this is what's going to be used to store the number of unique paths to any of these open tiles. So as an example, right, when I said, let's say there are three unique paths back from this tile, our starting point. Then in the exact same quadrant or in the exact same tile, I should say in our memory, it's going to have the number three right here. And so, like I said, when we're trying to figure out the number of unique paths from start to this adjacent tile. Whenever we're traversing the board and we get back to this tile, we can look into our memory and say, Oh, you know, we've already calculated there are three paths, so we'll just grab that number and use it and then just not continue any further. And so now at this point we're finally ready to come down into the code and figure out the solution for this problem. And just FYI, when I was editing this video here, I realized I made a mistake actually in this code, this line right here, it says if rho equals 0 or col equals 0, it actually should be. And this base case should be if rho equals 0 and col equals 0. So when you're watching the risk is video, just pretend that there are two ampersands symbols here, meaning and not or. And this is actually going to affect the final result of the computation when I do a little demonstration at the end of this video. So there are actually seven unique paths through this board here, not 11. And again, that's just because I made this little mistake right here. So sorry about that and just keep this in mind. Thanks. And this is the actual function itself that's going to perform this, these calculations. And I have most of the code written here already for you, but I do have a few question marks in place just to kind of force you to think about what these, these base cases should be in terms of what the values they should return. And so right off the bat, you should see some similarities here between this solution and the Fibonacci problem that you saw in the last video. And that we basically just have a few simple if statements that are the base cases. And then down here we have some recursion, right? We have basically have two recursive calls. And the results of these recursive calls are just summed together and stored in our memory. And so the way this is going to work is through our recursion here. We're going to initially start at our end tile and work backwards. So the recursion is gonna take us all the way back through this board, back to our starting tile. And that's the ultimate base case basically that I'll get into in a minute. And then once the recursion stops back at our starting tile, we're going to return backup through all those, those function calls back up the stack. And then we're going to fill in the number of unique paths to all these empty tiles along the way. Backup until we ultimately get to the end tile at the very end. And we'll have our solution. And just for your awareness, the way this board and this memory component are gonna be structured encode is user basically just going to be two-dimensional arrays, right? Basically just an array of arrays. And that's what you can see right here in our arguments of this function. We have our Board, which as you can see, is just a two-dimensional string array. And our memory, same thing, just a two-dimensional integer array. And the functions down here are just responsible for actually making the board itself and putting in some barriers and then creating the actual memory array as well. And the main function is just going to basically create the board, create the memory, and then just call our find unique paths function. And it's just going to print out the solution that it finds. And r n tile is going to be at the coordinate of 44, meaning row for column four. And remember, arrays are 0 index. So basically this is row 0, column 0. And so as I said, our end tile is in row 01234, column 012344, comma four, that's the coordinate of our end tile and our start tiles obviously at row 0, column 0. So that's how all that's going to work, coming back down to our function now, we can see two other arguments. This is the current row that we're looking at in the current call net we're looking at. And this function is first called from the main function with the coordinates of four comma four, right? Against starting at R n tile and then working backwards. And the way we work backwards is, as I said through these recursive function calls, or basically just subtract one from the current row that we're at, or subtract one from the current column that were at. So for example, when this function gets called for the first time, row is four and column is four. And then when we make these recursive calls, let's say we are looking at this 1 first. This is going to call finding pads again, except with rho equaling 34 minus one is three and then column four. And then looking now at this recursive function call is going to call the same function again with row four, but now column three. And as I said, these recursive calls are just gonna keep happening over and over and over again. Which is going to again, starting from here, slowly traverse our way back through our board until we hit some of these base cases, which are basically, you know, at some point we're going to hit a row, or a column is less than 0, since we're always subtracting from our current row or current column. And obviously we can't get to a row or column, that's a negative number. So we're going to return something there. Another base case is, you know, at some point we're going to hit a barrier. And obviously we can't go any further at that point. So we have to, we have to return something at that point. Or we hit our most simple base case, which is we just get back to our starting point in which case, you know, we can't go any further. And so we return some sort of value at that point too. And then of course, as we start returning backup through all these function calls, right, when these recursive calls finish, the results get obviously summed together and then stored in our memory array. So that at some point later down the road, if we ever come back to the same row and column again through some path that we're trying to calculate. Then we'll hit this case right here where we check our memory given the current row and col, now we're at, we'll see if the value there was greater than 0. And if it is, then we're going to obviously return some value in that case and not make any more recursive calls. And so now once again, I encourage you to pause this video and think about what these base cases should return, right? These are just integers that they're going to return some number. So go ahead and pause the video and think about what each of these if statements should return. Okay, so I hope you take a few minutes to think about that. Let's look first at this most simple base case, which is where we come back to row 0, column 0, which means we're back at our starting point. And so what should this base case return? Well, the answer is simply going to be one. And let's think about why first, second. So let's say through these recursive function calls at some point we get down to either this adjacent tile to our start point or this adjacent tile to our start point, right? Because, you know, let's say we are right here. This is row 0, column one. So at some point we're going to make this recursive call, which is going to send us to row 0, column 0. And that is going to, of course send us back to our starting point, the base case, which is going to return one. And that should logically makes sense because when that happens and we're back to adjacent tile, there is exactly one unique path from our start tile to this guy right here. And the same thing applies to this adjacent tile. This is row one, column 0. And so at some point we're going to make this recursive call, which is going to send us back to row 0, column 0. And that's, of course are starting location again, that's the base case. It should return one because once again, there is exactly one unique path from start to this particular tile. And so in both of these cases, we're going to store in our memory the value of one in the corresponding. Locations. And let me actually go ahead and get rid of this guy as well. So now this is the current state of our memory 11, which corresponds to this tile. And this tile, meaning there is one unique path to either of those tiles from our starting point. So now let's look at the next base case, which is this one right here. And this is the case where the current row or column that we're looking at is less than 0. And that will happen in cases like this where let's say game, we're back to here. And so one of these recursive function calls is going to send us, of course, back to our starting point. But the other is going to send us over here to basically no man's land. And obviously it's impossible to get to no man's land. And so in this case, we should just return 0. And that basically completes the entire case of, you know, if we were at this tile right here, because as you just saw one of those recursive calls that were gonna make sends us back to our starting point, which is the base case that returns one and the other recursive call centers out into no man's land. And that hits a base case which returns 0. And then of course we sum those two numbers together. One plus 0 is one, and this is where we store that value of one into our memory. Same thing applies to this adjacent tower. I hear one of those recursive calls sends us back to our starting point, that returns one. The other recursive calls sends us out into no man's land that returns 00 plus one is one. Alright? And so the next base case is this one right here. And this is the case where the current row and column number at actually has a barrier in place. And so obviously kinda with the no man's land base case, we can't possibly get to this particular tile, right? For example, there is no path from start to this particular tile because there's a barrier right there. And so just like with this no man's land base case, This one's also just gonna return 0. And so then we have our final if statement which has to do with our actual memory array. And so let's say for example, we are through our recursive calls in traversing through our board here that we end up at this tau right here. And again, we already have the numbers 11 stored in memory. So if we are at this tau right here, one of those recursive calls is going to send us to this tile. And then the other recursive call is going to send us to this tile. And for both of those tiles. When we get to this if statement, we're going to check our memory to see if there's any value that's been stored there. And indeed, one in one or both stored in their respective quadrants and memory. And so in those cases, we're just going to return the value that's stored there. And this is the key component of this entire solution here because this if statement is what allows us to skip doing any more recursion, which is basically just going to be more redundant re-computation of finding paths back to our starting point. And so ultimately if we are back at this guy right here, and one of those recursive function calls sends us over to this tile. And the other recursive call sends us to this tile. Both those function calls are going to return one. And so then in the end, when those functions return, we add the results together. So one plus one is two, and then that is the number of unique paths from start to this particular tile. And in the corresponding quadratic memory. That's where we started the number two. And when you think about this logically, that should make sense because in order to get this tile from our starting point, we can either go right and then down or down and then write two possible paths. And I hope you are seeing a pattern here so that as we are returning backup through all these function calls, we're going to be filling in the values in our memory array along the way so that by the very end, when we return all the way back up to our n tile, which is actually where we started in the beginning. We're going to have all these tiles filled in, in memory so that by the end, all I have to do is take the values that are stored in this adjacent tile. And this adjacent, adjacent tile. Add them together, and that's what's going to be the value, the number of unique paths, so to speak, from our starting point to our ending point. And so just as a little demonstration here that come back to my terminal. And I'll go ahead and compile the code. And then I can just run it. And again, all this is gonna do is it's going to execute this code. And for this particular board right here is going to find all the possible unique paths from start to end and just print out that number's. So if I go ahead and press enter, as I said in the beginning of this video, there are 11 unique paths and there you go. That's exactly what a calculated. And it did so very, very quickly. And once again, that's because it never has to do any redundant computation, basically recalculating paths back to our starting point more than one time. So even if this board was extremely large, maybe 100 by 100 tiles and a bunch of barriers randomly dispersed in that, in that board, it would still be able to run and figure out all the paths very, very quickly, as opposed to just a simple recursive method with no dynamic programming, no storage of values along the way. And with a board of 100 by 100, it would probably take a very, very long time to do all of that redundant computation. So I hope that all made sense. And in the final video coming up next, I'll be walking you through one more example problem that's going to be pretty difficult in my opinion. But once again, there's still gonna be a lot of similarities in how we build the solution for that problem from what you have seen in this video with this unique paths problem. And then also in the previous video with the Fibonacci numbers problem. So thanks again for watching, and I'll see you in the next one.
5. Coin Change (Hard): All right, welcome back to the final video in this course. And as I said in this video here I'll be walking you through one more problem that's going to be, in my view, pretty difficult in nature. You may encounter something like this in an interview or in school. But I would say on average, a question of this kind of difficulty would probably not come up too often. But if you understand this and work your way through the solution, have a good understanding of how everything works, then you'll be very well prepared and squared away for working your way through pretty much any dynamic programming kind of questions. So just diving right in here to the problem statement. The problem we're trying to solve in this video is going to be, so you are given coins of different denominations and a certain sum of money. And the point of this problem here is you want to write a function that's going to compute the fewest number of coins that you need to make up that amount of money. And of course, if it's not possible to use those coins, do you create that certain amount of money? Then we're just going to return negative one. So as an example, and this is the actual scenario that we'll be trying to solve in this video. So this array right here, which is stored in our coins variable, this is our array of coin denominations. So you can read this as who basically have coins that basically represent 12 Â¢$0.05, right? These are basically made up values for certain coins, but we basically have three coins and these are their respective values. And the amount of money we're trying to create through these coins is $0.11. And of course, keeping in mind that we're trying to do so with the minimum number of coins possible. So we can of course, with a coin that represents $0.01, we can just say, hey, we'll take 11 of these guys and there we go. We have $0.11, but obviously we have some other coins with bigger values and we can use them to create $0.11, but with fewer coins. And you can probably actually just sit here and look at this, think about it for a minute and come to the solution yourself in that, okay, the way we can create $0.11 in the fewest coins possible is we can simply have two of these guys, right? $0.05 each. So two of those would be $0.10. And then we just need one more. We can take this guy with $0.01, add them together. We obviously have $0.11. So in the end, we basically just need three coins to total this amount. That's the fewest number of coins possible. And that's what we want our function down here to return. So coming down to our function here. And this is the code I have written for you. Just like the last video, I have a few of these base case return statements just kind of with question marks because I didn't want to force you to think about it a little bit. These base cases should return, but you can see just by looking at this code here, it's definitely but more complex. There's more going on here. Still have generally the same format as in the previous videos where we have some base cases and we have some recursion here. And we are going to be storing results to our subproblems, which I haven't talked about yet in some sort of memory array or component. And using the solutions of the sub-problems to build up the final answer that we're looking for. So before I get into all the details here, let me come back to the top. And once again, I encourage you to pause this video and just take a few minutes to think about what these smaller yet very similar subproblems would be. That would allow you to solve this main problem here. So go ahead and pause the video and come back when you're ready. Okay, I hope you took a few minutes and think about that. And so I'll just dive right into the answer here. So the subproblems for this problem statement that we're trying to solve is going to be, well, you know, if we want to find the minimum number of coins in this case to add up to $0.11. Then before we can do that, we first need to figure out the minimum number of coins that create a smaller amount of money. And that's smaller amount of money is going to be the result of taking our initial amount and subtracting from that the values of each of our coins that we have. So as an example, we take 11, subtract one, that gives you ten. Then we do the same thing, 11 minus two for the second coin, that's nine. And then we do the same thing again for the third coin. 11 minus five is six, so we have 109 $0.06 cents left over after we subtract the values of each of our coin denominations here. And so for each of those smaller amounts of money, we need to figure out what the fewest number of coins possible would be that would add up to those smaller amounts. So the fewest number of coins that add up to $0.10, that add up to $0.09, and that add up to $0.06. And this is where the recursive pattern comes into play because in order to calculate the results for those smaller amounts of money, we need to repeat this process again. And for each of those smaller amounts of money, when you do subtract from them the values of each of our coin dominations. So for the small amount of $0.10, we repeat this process. Ten minus one is 910, minus two is 810, minus five is five. So 98, $0.05. Those are the even smaller amounts of money. And we need to figure out the fewest number of coins possible that add up to those smaller amounts. And then once again, this process repeats again and we have to subtract the values of our coins nominations from those even smaller amounts and so on and so forth, all the way to get down to the smallest amount of money possible, which is just $0.01. And then once we know the minimum number of coins possible to add up to 100%, which is just basically this guy right here. We have a coin worth $0.01. Then we can build our way back through all those smaller amounts of money into a fund to get back to the initial amount that we're given of $0.11. And so really in essence, what we're doing here is we're trying to figure out all the possible ways of combining the values over coins here to possibly equal $0.11, right? Every possible combination. And the way we do that is by the method I just described of subtracting each of these coin values from an, from the amount of money we're given. And they continually subtracting the coin values from those smaller and smaller amounts. However, if we were just to do that right, explore every possible combination of our coins here, that would be extremely inefficient because the number of possible combinations of your coins is going to be exponential. Meaning the more coin denominations do you have here in your input, the more exponential number of possible combinations of these coins you're gonna have to look through to figure out which combination of coins gives you the smallest number of coins. To equal the amount of money you're trying to initially is solved in the beginning. And so this is where our memory array comes into play, because as we are working through this process, right, I've continually subtracting these coin denominations or this subtracting their values from smaller and smaller amounts of money. As we're going through that process and we are figuring out the fewest number of coins possible needed to make up 12 $0.03 cents for sense, right? Building away back to $0.11, we can store those values, right, those fewest number of coin values in our memory array. So that if we ever come back down through all this recursion to trying to figure out again what the fewest number of coins that are required to add up to $0.04. Well, we can look into our array and say, oh, we've already calculated that before in the past, it might be two coins or whatever it is. So we can grab that value. And I have to compute any further down and just return back up and keep building our way back to this 11th sent number. Let me come back down to our coin change function here. And so the way this is going to work, and just first looking at the arguments here. So this coin changed function takes in three arguments. The first of which is our coins array, right? This is just our array of coin denominations that we are given in this problem. The second argument is this RAM, integer argument RAM is short for remainder. And this argument's going to represent the current sum of money that we are looking at within the context of this function calls. So this value is going to be started off as 11, right? Our main function is going to call our coin change function, and it's going to pass in the arguments of our coins, obviously, the initial amount of money we're trying to sum up two, which is $0.11, and our empty memory array. And then as we are subtracting our coin denomination values from our initial amount, $0.11. We're going to through that call this function over and over and over again. Every time we call this coin change function again, we're going to subtract a certain coin denomination value from our amount, and this remainder arguments going to represent that amount. So in the example I was describing previously, where we take $0.11 and subtract one sent, right? That's going to give you the result of ten. So at some point, when we call this function again, Rahm is going to be ten. And then later on when we subtract two from 11 is going to be nine and then so on and so forth all the way down. Ram is either less than 0 or equal to 0 and so on and so forth. These are the base cases again, right? And then of course, the last argument, as I've said, is our memory array. And so like I said earlier in this video, this coin change function has a very similar structure to the previous videos you've seen. We have our base cases here. And then this is kind of the new piece that is required to solve this problem. And it's just a simple for loop and it just does what I have described earlier in this video where for each of our coin denomination values, right? This for, for loop is just going to loop through each of our coin denominations. And for each coin, it's just going to recursively call our coin change function again with are same. Array of coins, the same memory array, but the only difference is we're going to subtract the value of that coin from the remainder amount of money that we have. And then down here, this is where like you've seen before or we simply take some of the results from earlier calculations performed by this for loop, and then we store the results into our memory array and then finally return it at the end. So once again, I want you to look at this code here and then pause this video and take a few minutes to think about what the base cases should return in terms of what integer value they should return back up the stack once one of these cases are hits. So go ahead and pause the video again and come back when you're ready. Alright, so I hope you took a few minutes and think about that. And so I'll just get into the answers here. So looking first at this base case right here, where remainder is less than 0. In this case, we should return negative one. And let's think about why. Well, as we are subtracting the values of our coin denominations from the current remainder amount. If we get to a place where remainder is less than 0, it's a negative number. We have obviously chosen a sequence of coin values such that when we add them together, we, we do not have $0.11, right? If for example, we are looking at the case where we take our initial amount of 11 and then subtract five and we get six. Do that again. Six minus five is one. And we do that again. One minus five is negative four. And that obviously, right, three coins with a value of five sets each equals $0.15. That's way more than our initial amount. So that is the case that we hit here, where remainder is less than 0. And we know from our problem statement that if we encounter a sequence of coins here that does not equal the amount of money we're looking for, then we should just return negative one. So that covers that base case. The second one is right here. And this is where remainder equals 0. And this is the case we're actually really looking for in this problem because whenever we get to this situation, we have found a sequence of coins equals in this scenario, $0.11, right? If we're exploring through all this recursive stuff, if we're exploring the combination of taking 11 minus five is six, then subtracting five again, so six minus five is one. And then taking our remainder of one and subtracting one from that, we get 0. And looking back, we chose two coins of $0.05 each plus one coin of one sense, that equals $0.11 in total. So that's why our remainder is equal to 0. And so in this case, we're going to return 0. That's because coming down to our for-loop here, when we are iterating through our coin array. And we call this coin change function again. Whenever it returns, we store the value in this variable result. And then we have this if statement right here. And we look to see if result is greater or equal to 0 and result is less than this min value here, which is initially set to some huge max integers, something like, you know, a 100 billion or a trillion or something like that. Some huge number. At this if statement passes, then we change the value of R min variable to equal result plus one. So as an example, right through all this recursion, as we are continually subtracting coin values from this remainder amount. Eventually we're gonna get to a situation where remainder equals one. And in that case, we're gonna go through this for loop one more time. I'm going to call recursively this coin change function with each of our coin values. And so if we take our remainder of one and subtract from that the value one, we get 0. And in that case, this base case will be hit. Remainder will be 0, we return 0. That's what result will be. Result is obviously greater than or equal to 0. And it is less than our huge initialized value of men. So that when we then we set min to 0 plus one, which is just one. And then we call this function again through another iteration of our for loop, where we take the remainder which equals one in this scenario, and we subtract from that, the next coin value of 21 minus two is negative one. So that will hit this base case. And when this function returns, result is negative one. Obviously negative one is not greater or equal to 0. And so this if statement will just skip. Then this for-loop repeats one more time. We take our remainder, which has the value of one, and we subtract from that the value five, that gives you negative four. And once again, the hits this base case, it returns negative one. If statement will then skip and then this for loop is complete. So now at this point, the value of min is just one. And suddenly hit d's little this if statement right down here. And we look to see if the min variable still has that huge max integer value in there. In which case, we went to set the index of one in our memory array to be equal to negative one. And this would mean that there is no way to create $0.01 from the coin denominations that we have. But of course, since one of the coin denominations we have an RA is equal to 100%. That's why this min variable has the value one stored in it. So this if statement is not going to hit. And so let me go to this else statement. And so then in the index one in our memory array, we store the value of one. And this means that the fewest number of coins that we need to create $0.01 is just one coin because we have one coin worth $0.01. And so that's why that value gets stored in our array there. So let me actually go up here, place that into our memory arrays. So in index one, we put the value one. Now let's walk through the scenario war remainder is currently equal to two. So we're trying to find the fewest number of coins that we need to add up to $0.02. And so once again, we repeat this process and the for loop, we take the value in remainder, which is two, and we subtract from that the value of each of our coin denominations. So we do two minus one is one, and this subtraction happens down here, right, where we call this coin change recursively again, and we do RAM minus coins. So two minus one is one. So we call coin change again. And now RAM is equal to one. And now this is where this other base case hits, where we look into our array and RAM is now equal to one. And so we looked into RA and we say, oh, the value of one is always start here. So we'll just grab that and return it. And so then one gets stored into our result variable. We go through this if statement. Obviously it passes because the result is greater or equal to 0 and it's certainly less than our initialized max integer values stored in men. And so now we change the value of min, right? Result is now 11 plus one is two, so min becomes the value two. And so far up to this point, this means that Right now we need at least two coins to create $0.02 right? After this coin change function returns, we're back to ram being equal to two. And so Nin equaling two means, like I said, we need to coin so far to create $0.02 and that would be just two copies of our $0.01 denomination coin. But of course we have two other coin denominations to look at. And so Nin could become even less Basically it could just be one that would happen if, as we are exploring these other denominations here, if we find that it is possible to create $0.02 with only one coin, then that's where you would change the value of man to become one. And you'll find this to be the case once we continue with this for loop here. So we go through another iteration, right? We take RAM wished his back to having the value two, and we go to our next coins, domination, which also has the value two. And we subtract those again right through another recursive function call two minus two is 0. And so in this case, we hit this base case, RAM equals 0 and we return 0. So once this coin change function returns, result is now 0. Come to this if statement. Obviously result is greater than are equal to 0 and it's also less than our current value of name, which is set to two. So now we reset the value of min to being 0 plus one equals one. So like I just said, if we're able to find another way of combining coins to create $0.02 with fewer than two coins. That's when we're going to change the value of men. And so now mania is one because we've found that it's possible to create $0.02 with only one coin. We still have one more nomination to look at. So this for loop is going to repeat one more time. So we take rim, which is two, we subtract from that the value of five, that's going to be negative three. So this is where we hit this first base case, right? Ran is less than 0, so we return negative one. Result is now storing the value negative one. If statements skips, and then this for loop is now done. And so let me come down to this if statement down here. And men is no longer equal to our initialized value of max int. It's been set to one. And so we come back down here again. And we said the second index in memory equal to one. So we come back up here. And so then this value in our memory array becomes one, which again means that the fewest number of coins that we need to create $0.02 is simply one coin because we have a coin that's equal to $0.02. And so as we are continually returning backup through all these recursive function calls, we are going to be filling in the values stored at each of these indexes and our memory array. So that by the end and the final index, we're going to have the value three stored here, right? This is the answer to this main problem that we're looking for three total coins to equal $0.11 and then we simply return it at the very end. And so then just as low demonstration, I can come over here back to my terminal and simply compile this code, and then I can run it. And of course this is going to execute our algorithm with this particular scenario in mind with these coin denominations and this 11 sit on Mount we're trying to add up to. So I'll go ahead and press enter. And then there you go. Our answer is, the fewest coins that we need to create. $0.11 is simply three coins. And once again, I was able to do all this computation extremely quickly because even though we are essentially trying to look at every possible combination of our coins here that may add up to $0.11. And then of those combinations, find the fewest number of coins since we are storing the results of some of these smaller sub-problems, IE, the fewest number of coins needed to create smaller amounts of money. Since we're storing these values along the way, we don't have to explore all the combinations of these coins in their entirety, right? Were able to start exploring one sequence or combination of coins. And then as we are exploring that path, we are able to look into our memory array along the way to see if we have already calculated some of these results in previous function calls. And in those cases we just stop, take that value and then we don't have to explore that particular sequence of coins any further. And so this will save a huge amount of computation and time, especially when you have a lot of different coin denominations. And the amount you're trying to add up to is very large. So I hope that all this made sense. Again, I know that this particular problem is quite difficult to work your way through. So if you are struggling a bit to understand what was going on here, I highly recommend just watching this video maybe a couple of times, looking at the code in particular and trying to walk yourself through it. I do have each of the code files shown in the videos in this course posted in the project section of this course. So you're more than welcome to go there and download the files and take a look, run them if you want to make changes at print statements, whatever you need to do to really understand how this stuff works. So thank you for watching and I'll see you in the final video coming up next just to wrap some things up.
6. Wrapping Up: All right, so at this point you have completed the course. I hope you're able to learn a lot from it and tell it, give you some practice with solving problems using dynamic programming. You can take a look at the course project down below. And so that being said, thank you so much for watching this course. I do appreciate any and all feedback that you may have. I M scott Reese again. I do try and publish one new course every two weeks. And please do also check out the other courses that have on skill share. Or they have a lot of content published on computer science lead topics like this, as well as other courses on trading and investing topics as well. And don't forget to also follow me and skill share so that you'll get notified every time I come out the new course. So thank you again for watching and happy coding.