Finding Optimal Paths - Dynamic Programming

Key Takeaways

in this video we'll be using an algorithm technique called dynamic programming to solve a specific question namely the question here is given some kind of grid it'll be a square grid but the size can be anything this is a 3x3 for simplicity but it can be a 5x5 10 by 10 anything you want and some numbers inside each square we want to find the path that gives us the most value starting from the lower left-hand corner and ending up at the top right-hand corner and other restriction is we can only make moves that are either going up one block or going right worth one block so we can't go left words or down one block so for example just as an example of what us path might look like we're starting at the star and we have to end up over here at this three so one path easy path that we could do could be simply starting at the star and going upwards all the way and then doing right works all the way so how much value does that generate so that path gives us two three four five six seven so are there better paths so with an example as small as this you can probably find the best path but as the example gets bigger we need some kind of generalized framework to find the path so let's go ahead and you look at the problem backwards that's going to help us a lot so we have to end up at this three which means we have to collect this three so how do we end up at this three are the move before that can either come from this one or this one because we can only go right words or upwards so it has to come from one of those two blocks so let's before we go into that let's make a list of generalized values so we're gonna have P and we're gonna have I J so they're gonna have some matrix P and it's going to be the same size as our block right here so this matrix P let's just draw it in it's gonna look like this and for this matrix P the index I and J so 0 1 2 0 1 2 for example 0 2 that's corresponding to this final block right here tells us what's the longest path what's the most value you can generate if we start at the start and end at that block so the thing we actually want is p 0 2 because we want to know what's the largest value we can generate if we start at the start and end at the sub block 0 comma 2 which is indexed by 0 comma 2 but we also have values for every one block here for example what is the one given by P 1 1 well that corresponds to block we index 0 1 0 1 so it's the middle block right here this - this is asking what's the biggest value we can generate if we start at the start and end at the block 1 1 and as we can see by inspection there's only two ways to get there either we can go to 2 or 3 - and obviously 3 2 which gives us 5 is better than the two - which gives us the 4 so you're probably asking why are we doing all these intermediate problems if what we really want to solve is this one why do we care what the intermediate problems the reason is because we can form a recursion a recurrence relation that tells us the answer to this problem based on the answers to some previous problems and let's see what I mean by that so specifically if we want this is 0-2 we want this p0 to write what is p 0 - remember this is asking what's the most value we can generate starting at the star ending at this 3 so the key thing here is we ended at 3 so we had to collect that 3 as part of our value so p0 2 has dinkler the 3 plus and now as we said before we can either arrive at this 3 from this one or this one so this one is indexed by what it's p 0 comma 1 and this one is indexed by what it's P 1 comma 2 okay so the highest value can generate starting at the star and ending at this right here this 3 is taking that 3 plus the maximum and I'll explain this in a little more detail in just a second the maximum of P and we're gonna index those blocks again by 0 1 0 1 and P and this block is indexed by 1 comma 2 1 2 so what is this mean let me put this in brackets right here so this is telling us the maximum value can generate starting at this star and ending up at this 3 is 3 of course because we have to take that 3 if we're gonna end up there plus the most value we can generate starting at the start and ending at this 1 or the most value can generate starting at this star any of this one for example let's say the max value can generate starting at this star and any of this one is some number 8 and let's say starting at the start ending at this one is some number B so let's take the higher of an be let's say its B then if we take the higher of a and B and we add 3 we're gonna get the best possible value we can get starting at start ending at three because there are only two ways to get to three are three through these two ones right here there's no other way so we've exhausted all the possible options and we can kind of generalize this a little bit because we can say this was 4 0 comma 2 but we can say for any IJ for any IJ the maximum value we generate from starting at the start and ending at that I J sub block is the value at IJ so I'll just put value at IJ and this is just 3 because the value at 0 comma 2 was 3 so of course when we end at some sub block we have to take its value plus again the same structure the maximum of two things so when we are at a sub Luck we either got there coming from the left or coming from below and there's certain corner cases here where for example if we're trying to do it for this guy we could only come from the left there's nothing to come from below so if we're writing a program it's really just an if statement you see if it's possible if you're on one side of the board or not but in general its maximum of and let's follow this formula so it's you keep the eye and then you reduce the J by 1 so P I J minus 1 and the other option is you keep the J and you reduce the I by 1 so P that's a slight correction right here so we saw here the other one was we have to increase the I by 1 and we keep the J the same so this should be a plus sign so just note that change right there and this is a generalized framework this works for any point keeping in mind that for certain points one or more of these values won't exist and the last thing we have to do is with any recurrence relation we have to give the base cases so our base cases in this case will be this guy right here and this guy right here so we feed into this matrix right here that this this is given by what this is given by 1 comma 0 and the most value can generate starting here and going here is obviously 2 there's no other way to get there so we say that our P 1 comma 0 is going to be 2 for sure and the same reason this is going to be 3 for this we don't have to give it we can just give a 0 because there's no real meaning to starting here and going nowhere and then we can just kind of fill this end for example let's look at this guy and let's follow it what is the maximum value we generate starting at the star going to this block right here as I said before it's 5:00 but let's use our framework and justify it so we're trying to find P 1 comma 1 so it's gonna be the value at 1 comma 1 ie 2 plus the maximum of we're keeping this one 0 so it's 2 or and this is gonna be 3 right because it's gonna be 2 comma 1 so it's gonna be 3 plus 2 is the highest so it's gonna be 5 and you proceeded in that manner so let's just do the rest of them so what about this one what's the highest value can generate starting here and going here we see the only way to do that is going straight up and by symmetry the only we get this 2 is going straight across so this is gonna be 3 and this is gonna be 5 3 & 5 and now what's there's only 3 more to do what's the highest by you can generate going here here we have some options so you take that one for sure you can either come from this 3 or this 5 we would rather come from this 5 so we can get a 6 here what about this guy we can either come we will get that one for sure we can either come from the 5 or the 5 in this case doesn't matter it gives us the same exact answer of 6 and now here we it doesn't matter which one you come from because we're gonna take this 3 and add it to the 6 or this 6 giving us a total of 9 so we've answered the question we found that the most value we can generate starting at the start ending up at the block P 0 comma 2 is going to be 9 that's the most we can generate and if we were careful in our program and we kept track of which path we took each time we can even find the exact optimal path what that means is for example we want to know how do we get that 9 which path are we supposed to take well all we have to do is just do some careful bookkeeping which is you start at the start remember to get to this 5 we had to go 3 and then 2 so 3 and then 2 and then to get to either of these ones we just we were to get either of these sixes rather we chose we said that since they both end up being 6 we can go either way so we can go either this way or this way in this case we have a branch many times the path will be unique in this case it is not and we said to get this 9 we could have come from either of these sixes so we can go like this and like this and in fact actually we also could have gotten this 6 by coming from this 5 so we also go taking a branch here and going up here so there's actually many paths weirdly enough in this case to get to our final answer of nine namely they're the paths are we could have taken fully right and then fully up so fully right and fully up that's one way to do it we've could have gone right up right up so right up right up that's another one you clear done we could have done right up up right so right up up right is that all of them so yeah indeed it is so we have these three we have one two three ways to get our maximum value of nine and this is a very toya example this is a three by three so if you're coming here from the silly fish video you know that we have a five by five example and in the computer program we actually did ten by ten so it's all the same that's how I found the optimal paths in the computer programming the code is just reflecting all this statements we have right here honestly all it does is its goal is to find the optimal value starting from the star going to the upper right hand corner and it just works backward it says okay I have to end up here I can come here from here or here and I can come here from here or here and just does that then it finds the optimal value in that way using those recurrence relations now quick note if you are coming from the silly fish video we also had a rule in that video that said you can come from the right you can come from the bottom or you can come from the diagonal now you realize now how ridiculous that rule is because you would never want to come from the diagonal and the key point is that let's say you were at this too and you wanted to end up with this three if you can come diagonally to that three you can go up over or you can go over up you would never want to go diagonally because if you went diagonally you would just capture that three whereas if you went over and up or up and over you would capture that three plus whatever positive value is in this squares so as long as these have positive values you never want to connect and that's why in those optimal paths we see none of them have diagonal diagonals but the genetic path sometimes do have diagonals which is interesting in itself so we might do somewhere in dynamic programming later on but this is the general idea of dynamic programming you form these recurrences between your problem because you have a final problem but you need to find the subproblems before it to solve that final problem so hopefully this helps a little bit and until next time