Cherry Pickup II - Leetcode 1463 - Python

Key Takeaways

hey everyone welcome back and let's write some more neat code today so today let's solve the problem Cherry pickup 2 this is definitely a hard one but it's not crazy hard at least in my opinion it's not as hard as the first one which is why I'm not going to recommend that you solve the first one before this one this one in my opinion is easier so we're given a matrix let's just focus on the visuals here and we have two robots they start at the top left and the top right of the grid and for each robot we have three choices on every move we can either go down left down or down right and the other robot makes the same or or not the same choice but it has the same set of choices to make so it can go here it can go there or it can go there so maybe this one goes down this one goes over here and they both make choices at the same time so they're always going to be in the same column now given this each robot picks up all the cherries or whatever thing you want to consider it takes the value in the position of the grid that it lands on and we want to determine the paths of both of these such that we maximize the points or the cherries that we collect and that's what we want to return so in this case you can see the paths are going to be like this and here like that so the total for this is going to be 24 now they also tell us that if both of the robots land on the same position then both of them can't pick up the value only one of them can pick up the value so you might think we need some additional logic to handle that but my claim to you is that we are guaranteed every value in this grid is going to be greater than or equal to zero why would we ever want both of them to land on the same position that would never lead to the maximum result because we are guaranteed the grid is always going to have at least two columns why would I ever want this value to be in the same position even if there's a big value there cuz they both can't collect it so I'd at least want this guy to collect something over here it'll get something that's greater than or equal to zero and if both of them were to land in the middle our set of next choices would be limited to only three but if I have one over here and one over here now my set of choices is going to be at least four so again why would we ever want them to land on the same position next we kind of think about this in terms of choices it's not hard to kind of visualize this as a decision tree because that's kind of what we're doing you might think before going down the brute force method the backtracking solution you might think is there a greedy way don't we just want the robot to pick the maximal of its choices not necessarily because what if this guy says Okay I want to take the five because there's a one here and there's a one here but what if there's 100 over here we can't be greedy and take the five we have to take the one in this particular case so we can then get the 100 no point in trying to be greedy we do have to consider all possibilities we don't know what lies ahead now when you think about the Brute Force you think what are the parameters of the Brute Force going to be the base case is kind of obvious once we reach the last column we can't really go any further and we do have to do this simultaneously because we do have to make sure that both of them don't land on the same position cuz we definitely don't want to overcount the solution we don't want to collect the same value twice so we do have to maintain what is the column of the first robot I call that column one column of the second robot I call it column two now you might start to be naive you might start to think we need another parameter Row one for the row of this robot and another parameter Row Two for the row of this robot but remember it's easy to miss this they are always in the same row so we only need a single parameter for the row this is actually enough when we take this Brute Force solution and optimize it with caching which I'll show you how to do in the code we can actually pass this problem that's why it's not like a crazy problem in my opinion now what does the decision tree look like for a single robot we have three choices but we have to make a choice with two robots so it's not that we have six choices let me make this very clear we don't have six choices we have nine choices three times three because we consider the case where this robot goes here and this robot goes there or the robot goes here or the robot goes there that's three choices the next three would be this go down this one goes here or here or here that's another three choices and I could continue with the rest of them but you get the point that's what we will consider as well and then let's consider one possibility where let's say we go here and then this one goes here next we will recursively make the same nine choices in terms of time comp complexity this looks like 9 to the power of how many columns we have or the number of rows sorry about that I always get those confused so it's going to be something like this 9 to the power of R of course we want to optimize this we know the parameters are going to be row column 1 and column 2 what are the possibilities for this well R could be the number of rows I'm just going to use capital r for that for each of these it's going to be C so time c^ 2 that's the time complexity that's also the number of sub problems so this is the size of our cache when we apply caching when we get to a sub problem we don't always want to recompute the result so we store the result of it in the cache okay let's code this one up let's start with the DFS it's the recursive Brute Force solution and I'll add caching to it at the end so we have the row column one and column two the base case is well the main base case is going to be when we reach the last row so if R is equal to number of rows minus one I should probably compute that so we have number of rows and number of columns I like to do this just because it makes things more readable that's also why a lot of people you'll see will use I and J for rows and columns but I think that's less readable it's very very clear what we're talking about when we have R and C so I prefer this this base case is when we reach the last row in that case we are just going to Simply return the sum of the values in the positions we know they're both in the same row so we can do it like this the value at column 1 and the value at column two from the grid but what if they were the same what if column one and column two is the same we probably need another base case to check that we don't want to overcount the solution like I said so let's check if column 1 is equal to column 2 let's return zero let's just not consider that it'll make our life a little bit easier but there are other cases where we might want to return zero I didn't talk about it in the drawing explanation but what if we go out of bounds well the row is never going to go out of bounds we keep moving down until we we reach the last row but the column could go out of bounds it could be that the column one or column 2 is less than zero and the easiest way to check that is take the minimum of both of these this is kind of a shortcut take the minimum and check is the minimum less than zero or opposite take the maximum of both of them and check has that gone out of bounds is the maximum equal to the number of columns that's the only way it would go out of bounds if that's not the case let's go ahead and compute the result so I'm going to compute the result initialize it to zero actually and then out here we're going to return it but now's the fun part how do we enumerate all of those nine decisions I don't want to write nine recursive calls so the easiest way to do this is two Loops I'm going to call this c1d the delta or the difference in C1 we know we can either move the column to the left I'm going to call that negative 1 we can either keep the column the same I'm going to call that zero or we can move to the the right I'm going to call that one and we can do the exact same thing with column 2 so just have this hardcoded array I probably could have saved a little bit of space I guess if I put this in a variable but it really doesn't matter now is the recursive call when we call DFS what are we supplying here well the row always increases by one that's the easy part row plus one what about column 1 and column 2 well that's why we have this Delta column 1 is now going to be C1 Plus the Delta and C2 is going to be the same C2 plus the Delta and we're trying to maximize the result so let's just set result equal to the maximum of the result and the maximum of the recursive call there's one thing I missed here as we are traversing the grid shouldn't we pick up the cherries at this position so far we only pick it up in the base case I should here be adding to the recursive call this value right here but that's going to make this line really really long so I'm just going to choose to do that here before we return the result let's just go ahead and add this to the result because we know this is a constant and it's going to be added to every single call here so instead of doing that here I'm just going to do that out here so result plus equal to this and then return it this will pass um let's just finish it up so when we call DFS the row starts at zero column one starts at zero and the second column starts at the number of columns minus one all the way top right so this does not pass but we can just add a little bit of caching and then make it pass so I'm going to declare a hashmap for that and here I'm going to add the if statement is this key all ready in our hashmap if it is go ahead and return it if it's not go ahead and compute it and then return it so when I compute it I'm actually going to store it right in the cache so I'm going to do this now result plus that and then I'm going to return that just like this and it looks like I have a little typo here don't know why I put R1 here and now we also have R1 up here sorry about that we also have a little typo here I forgot to take the maximum of these we don't want to assign the result to a tupal and another R1 here but other than that let's run the code and you can see it works and it actually is pretty time efficient this is about as time efficient as you can get it but we can improve the memory so right now the memory is three-dimensional it is going to be the number of rows times the number of columns squared we can actually improve that because you notice if we're Computing this problem we only need the result of the sub problem from the next row this row depends on the next row we don't need every single Row in memory at any point in time so when we implement the tabulation method we can improve the space complexity to actually be c^ S the number of columns squared let me show you how I'm going to do that so I mentioned that we don't need the memory for every row to be in memory at the same time instead of like going recursively we compute the solution top down we can work our way up we can compute this bottom row what is the sub problem of the bottom row it's basically if robot one and robot 2 were to be in any combination of those positions what is the maximum result we could get for example consider like if robot one is here robot 2 is here to compute the value that goes here we would recursively well not recursively but in our solution we would try all those nine possibilities I talked about but we'd kind of go out of bounds wouldn't we so let's just implicitly put a bunch of zeros here so we don't have to consider the case where we go out of bounds this way of visualizing it is not entirely enough actually because what we found is our space was three-dimensional and we reduced it to two dimensionals at least Le that's what we're trying to do and that 2D grid is going to look like column squared it's going to be the number of columns which in this case is three and we're going to square that so 3x 3 now what does this represent let's say this is column 1 this is column 2 we're basically saying if robot one is at column 0 and robot 2 is at column 0 what is the result going to be well we skipped that because we don't consider the cases where they are equal remember so that's easy enough what about when column 1 is at zero and column 2 is at column 1 that's going to be over here that case it looks like we'd get a 2 + 1 and then we'd put a three over here and we can do the same thing here in column one we have a two and in column two we have a one this is column zero sorry about that so here we'd also put a three and you'd kind of just go through all of them and do all of that fill those values in even though it's really hard to visualize this cuz this is three-dimensional we're going to have these stacked on each other and we're trying to reduce that now to two Dimensions so what I'm saying is okay we compute this first one I'll just kind of fill these values in 1 and Z is going to be the same as 0 1 so we'll put a three here 2 0 is going to be the same as Zer of two it doesn't really matter which robot is in which position so we'll have a three here 2 1 1 two are going to be the same which is going to be 1 + 1 and that's going to be a two here and a two there so at least in the last row if we were trying to maximize the result the most we can get is a three that's what we've discovered so far now one more optimization I'm going to make if we were trying to fill in this grid we'd need two nested for Loops iterating over the number of columns right but we actually don't need that I'm hypothesizing we can actually only fill in this part of the grid and skip that part it doesn't really improve the time complexity this is still proportionate to c^ S but it's it's just an easier way to code it up and you'll see that when I code it up basically what I'm going to say is for C in range from zero all the way up until the number of columns minus 2 and actually I think even this is more than we would need because when you look at the picture over here would we ever want the two robots to cross each other would I ever want this robot to end up on the other side of this robot probably not because it doesn't matter which robot picks up what we care about the total that we pick up so if we were ever able to create a path like this we could have done the opposite and created a path like this so why would we ever want the robots to cross this is something that's not super important but knowing this can actually make the code a little bit easier to write so that's what I'm going to be doing so this is what we computed for the last row now let's compute the next thing for the next row and I'm not really going to do a lot of it let's just consider this one cuz we know this is what ends up maximizing the result so where robot one is at column one and robot 2 is at column two so we're looking at this and this so how do we get the value that goes here well we of course take the values existing in the current position so we'd find a five here and a five here we are keeping track of another variable remember the current row that we're in we're working our way up as we do this and remember to compute this row we only need this Row in memory and the word row is misleading because the values for this row actually are represented in a two-dimensional grid so what I'm saying is let's say this is our DP grid our previous DP grid and I'm right now Computing the current DP grid of our current row also I think I was wrong when I said we're at this column I'm sorry I don't know what I was thinking robot 2 is here of course it's at column 2 so we actually want the value that goes here but yeah the first thing we do is take the values of this that's 10 and now we want which one of the sub problems was maximal again that's nine different possibilities so basically we look at the grid and just so you know coincidentally the size of this grid is nine and that's because the number of columns is 3 * 3 that's not always going to be true it could have been possible that this grid was 5x5 even if the grid was 5x5 we still only have nine other choices that we would be looking at I want to make that very clear this is simple for us we have up to nine choices to look at and those nine choices would be basically this or this we really don't have many choices there's really actually only two valid choices either robot one goes down and robot two goes here or robot one goes here and robot 2 goes over there all other choices are invalid because we don't consider when they're on the same we don't consider when one goes out of bounds so there's two choices and it looks like this one one is maximal where is this stored by the way in 0 1 0 1 the value is three so we take what we computed which was 10 + 3 and store that in this position which is 13 so that's what you would pretty much do filling in this entire grid pretty much now since we only want two of these in memory at a time we would take all these values move them up here this is our previous DP and now we'd compute the next one our current DP as we work our way up as we get to this row and then eventually this row when we're finally done what value are we going to return well we know we started here and here so whatever our DP array ends up being we will return the value that is right here column 1 is zero column 2 is the last column so this is all the memory optimization and the tabulation solution basically the space is going to be number of columns squared let's code it up so I'll leave this code here but we aren't going to be reusing any of it but sometimes when you're writing the bottomup solution referencing the recursive solution can be helpful first thing I'm going to do is just declare our previous DP grid and like I said I'm going to default assume that they're all zero so we're implicitly saying every value below the last row is implicitly zero so just like that and I want to work my way bottom up some people don't like that because you have to go in reverse order so this is what I do you don't have to write it that way but then if you write it the other way you end up changing the logic of the problem kind of a lot and that makes it very different from the recursive Solution that's why I prefer doing it this way but again you don't have to now for this row we're trying to compute the current DP so all I need to do is just copy that and assign it here okay so next we want to enumerate all of the columns so column one could be in any of these valid columns column two could also be any of these valid columns but like I said I want to take a bit of a shortcut I know column one is never going to cross column two so why don't I just put columns minus one over here for column two I'll put column 1+ one because I don't want this to start at column 1 that would mean they're at the same position then I go up until tell the number of columns this way not only do we not consider the case where they've crossed each other which would be redundant but we also don't consider the case where they overlap we don't need an if statement now to check if they overlap that's pretty convenient I even would consider that pretty Neato so now for this sub problem we want to compute the number of Max cherries and for us to do that I'm going to assign this to zero and after we have computed the number of Max cherries we want to store it in the current DP grid and what is the sub problem that defines the current DP grid is C1 C2 I don't need to put the row here because we automatically know current DP corresponds to the current current Row the previous DP corresponds to the previous row AKA row minus1 but how do we enumerate those nine decisions well how did we do it recursively it looks like I just had a couple nested for Loops I can just copy and paste that it's just that easy now we're getting five layers of nesting deep so I might as well show you a bit of a shortcut that I actually learned today we can take these C1 C2 and we can enumerate them by taking the product of two arrays so I put the first array as this and the second array is going to be the same so when we say product we're just considering all combinations of this the first of them is going to be assigned here the second is going to be assigned here so it's pretty much doing what we had earlier we just don't need to do one extra layer of nesting with this Delta I'm actually going to put the new columns in separate variables cuz we're going to be needing them many times so just like this column 1 and column 2 now while we don't need to consider the case for column 1 and column 2 are equal we kind of do need to consider the case where the new column 1 and new column 2 are equal don't we shouldn't we consider that case no because for this if we try to reference current DP or the previous DP the value stored there is going to be zero because we never assign it in the first place we never consider that possibility so we don't need to consider when the column or the new column are equal but we do need to consider when the columns go out of bounds new column one could be less than zero new column 2 2 could be less than zero actually it can't because we guaranteed that's not going to be the case they never cross each other column one is always going to be on the left column 2 is always going to be on the right this simplifies things even more for us now we check is a new column 2 equal to the number of columns we don't need to check if column one is it never will be if that's the case by the way we just continue we skip that if that's not the case we want to compute the max number of cherries well what's the current number of cherries it's it's going to be Grid at the row column 1 plus Grid at row column 2 and we can probably just move this up because this is not changing within this loop we're using the original column so I'm actually just going to take this and move it up this is the current cherries this is the max cherries now to compute the max cherries we can say Max cherries is going to be equal to the maximum of itself or the result of the number of cherries in the current position plus the sub problem this is surprisingly the easy part how do we know where the sub problem is it's in the previous row aka the original DP grid and what are the coordinates of it is it column 1 and column two or is it the new column 1 and new column two well if we're starting at column 1 and column two and this decision represents the sub problem we have to consider all nine valid sub problems then of course we want to do the new column one and new Colum column 2 and if you look down that's exactly what we did in the recursive solution when we call DFS so nothing crazy lastly we want to out here before we do that over here current DP should be assigned to Max cherries after it's been computed and also we always want to update our previous DP with the current DP after it has been computed so just like this and what is the return value again well it's going to be stored in DP the coordinate is going to be the First Column start starts at zero last column starts at number of columns minus one so this is the entire code a lot of work usually the tabulation method is not this much code I mean there probably are ways we could make this more concise but I didn't want to like make it too unreadable so hopefully you can translate this into other languages if you're trying to do that let's run it to make sure that it works and it does it's pretty efficient you can see for once leak code is actually accurate this solution is definitely memory efficient if you're preparing for coding interviews check out ncode doio thanks for watching and I'll see you soon