Maximum Number of Points with Cost - Leetcode 1937 - Python

Key Takeaways

hey everyone welcome back and let's write some more neat code today so today let's solve the problem maximum number of points with cost this is a pretty interesting problem because to be honest even the Brute Force solution will lead us down the dynamic programming path and I'm not talking about the recursive solution like I guess you'll see we're given an integer Matrix it doesn't necessarily need to be a square one but this one happens to be the idea is that we want to pick one element from every single row so I guess it doesn't really matter whether we start with the first one or the last one so I will start here just cuz I think it makes more sense so in the first row we can pick any of these elements and we will get that score so in this example let's say we take three the next choice is going to be more interesting though so the idea is that if we pick this element here we will add a score of one if we pick this element here we're actually going to add a score of five minus one we subtract one because it's one spot away like in terms of column like we have to go one Colum that way to get this element and if we were to pick this element it would give us a score of 1 - 2 cuz this is two spots away so in this case we will take this one so we'll get a score of four so lastly we have the exact same choice if we pick this one we're one away so we would get 1 - one here we're at the same one so we would just get the score of one here we would get a score of 3 minus one because this is one spot away from the previous row think of that how do we even solve this solution ution in a Brute Force way well you might go down the recursive path like for each element in each row we will have a choice and technically you could do it that way but I'm going to show you that there's a very natural dynamic programming solution to this as well so in the first row let's just say we have that in memory and we don't really need to do anything there so let's just say like this is what we start with the next row we want to know if we were to take this element what is the max possible score we could get well it's it's going to be 1 plus something from the previous row so the choices are this we either get 1 + 1 that would be this way picking like this as the previous element or we could do 1 + 2 - 1 that's picking the next element and lastly we could do 1 + 3 - 2 that's picking this one because it's two spots away from it it looks like all of these are actually the exact same so this clearly took us one Loop to figure out what the max element here would be and I think it's just going to be two we're going to do the same thing here so we have five here I should use a different color so you can actually see it but five over here that's the element we're going to be getting from the current spot but now the choices are this either this which is 5 + 1 - 1 because it's one away and then the other choice is going straight up which is 5 + 2 and the other choice here is going that way which is 5 + 3 -1 we could probably pick either this or this both of those will sum up to the number seven so that's what I'm going to put here and lastly we do the same thing for the one that's over here so just to go quick it's going to be uh 1 + 3 that's 4 or 1 + 2 - 1 that's 2 or 1 + 1 - 2 so it's going to be 1 + 3 that is four now we have this row next we would want to compute the elements in this row and we would find that we only need the previous Row in memory at a time to compute the next row we would pretty much just be able to deallocate this from memory so we will have two variables let's say one is going to be the row the previous row and then the next variable here I might call uh the next row but just to quickly fill in the values here we would get the three from there 3 + 2 that's 5 or 3 + 7 - 1 that's going to be 9 or 3 + 4 - 2 which would be five so 9 is the biggest value that goes there and then here we would kind of do the same thing 1 + 2 - 1 1 1 + 7 1 + 4 - 1 so it's going to be 1 + 7 that's 8 and then lastly here 1 which is the value that's over there plus this that's 5 or plus this - 1 that's 7 or 1+ this - 2 yeah the these are the values in the last row and now you tell me what would we do right at the end so now let's say this is out of memory these are all the values well we would probably pick the max value from this row that's nine that's the expected result for this problem now if you're paying attention you saw that the number of value Val we're going to have to fill in is pretty much going to be like one for each position in The Matrix so that's going to be o of M * n let's say those are the dimensions of the Matrix for us to actually populate a single value remember that we had to Loop through the previous array so that is going to be M * n 2 let's say n is the number of columns in terms of space it's not too bad I think it's just one or two arrays in memory at a time so it's going to be Big O of n now the question is can we do better can we somehow optimize this runtime and the answer is yes if you were paying attention you might have noticed a little bit of repeated work it's not super obvious though so like intuitively you can kind of tell that there is a bit of repeated work going on but it's not obvious how we can eliminate it so let's get into that remember what we did this is the first row we're trying to fill in the second row and initially like we can say that like these are the values here 1 151 but to this we want to add the maximum choice we could make among the previous ones it's not as simple as just taking the maximum of all of these values if it were that would be repeated work that we can easily you know reuse for the other spots but it's not that simple what we did was we took this element by itself we took this element minus one we took this element minus 2 and then among all those we can sort of keep track of what the maximum was we can do that like as we go the idea is that we want for every single element to just be able to look at a single element and just reuse that the problem is that we can't because to compute that element the candidates are going to be different for every single one so you're going to still have to have three choices but we can actually split it into two elements so imagine that like there's two subarrays here one is going to be called Left well they're not subarrays they're like actual arrays and one is going to be called right this is how we're going to populate it so here it's just going to be one and then here it's going to be the choice of two because that's the choice that this guy would get he could pick two itself or he could pick the value here minus one and so we're going to use the sum that's here and L makes sense when we get to this point but so it's going to be 1 minus one so what's bigger 1 - one or two well obviously two so that's the choice here and then for this guy this guy can pick between just three itself or the previous sum minus one the reason at this point why we don't have to look at all of the elements the reason we only have to look at two is because this number represents the max among the last two choices but those two choices were made for the element in this position so the only thing that we would have to do from here is just subract one from it cuz this is the max choice that this person has so if we wanted to make that choice though we would have to minus one from it cuz we are a distance of one in a way like this is like double dynamic programming we're reusing rows and we're reusing elements as we kind of populate this array left to right so here the max choice would be three now keep in mind that these values only tell us what's the max sum that we could pick from this that would include this choice this choice and this Choice well that's for this spot but this guy this only includes the choices from here and here it doesn't consider the choice from there same thing this way it only considers if we were to choose here but it doesn't include the choices from there and there so this was named left we're filling them in from left like this and this and this so let's do one from right which is going to go in the opposite direction you know maybe we should swap these names I don't know that's up to you but here it's just going to be three so we can actually just leave that as is and then when we get to this position we're going to say okay either I could pick the value here which is two or I could pick 3 minus 1 they're both going to be the same so it's two either way and the value here I could either pick one or I could pick 2 - one so that's going to be one again so this time they were both the same but that's not necessarily always going to be the case uh to compute the values that go in this row we would just take the maximum of these two they're both one in this case so we would get a two over here for this same thing Max of those two we would get a seven over here same thing here 1+ 3 that's going to be four let's continue from the next row so once again we are going to create these two temporary arrays which I call left and right this one will be built going this way this one will be built going the other way and so this time it might be a little bit more interesting so here we have two itself here we have seven seven or this one minus one well seven is bigger okay so this one which is four or the previous one minus one that's going to be bigger so we'll have six which is 7 minus one this is basically saying that this guy if they had a choice they could either pick this element or they could pick the maximum among these that value is already stored here seven is the maximum among these so what choice should we make this one or this one minus one well it's going to be six so that's what the value here represents the value here represents the max choice that they could make from this and this the value here represents the max choice of just this so now going the other way we want to include the other choices this guy could also have chosen that this guy could have also chosen that so um we here we'll just initialize it with four cuz that is the sum from here so that's four here we can either pick seven or we could pick the value to the right minus one we will definitely pick seven and here we could either pick two or the value to the right minus one that's what we're going to do which is six so now to know the value that's going to go here we just add to this the maximum of these two it's six so then we would get nine over here same thing here one plus the max of these two that's going to be eight same thing here 1 plus the max of these two that's also going to be eight so this way we can populate each row by going through three passes this is one pass another pass and then actually populating the values we could get that down to two passes if you wanted to like as you're Computing the second row you could have just taken the max of that and just added it to this one rather than building this row itself but that's not really an optimization that's going to change the overall time complexity so I'm actually just going to ignore that and we've gotten the time complexity though down to M which is the number of rows and then three passes which is 3 * n but that doesn't change the overall time complexity which is M * n space complexity is just the length of a row which is O of n okay now let's code it up so as per usual I'm just going to get the dimensions of the Matrix first so the number of rows and the number of columns in an individual row and then we're going to go row by row we're going to start at the first row that we're skipping the row at index zero but we are going to store those values in a variable which I'm going to call row we're not really creating a copy of it we're just doing this for convenience but now we are actually going to create a copy of the current row that we're at you don't have to do it you could overwrite The Matrix but I think it's generally better to not do that so I'm going to call this next row this is what we're ultimately going to be Computing and I'm initially just going to set it to the current row and create a copy of it now I'm also going to create those left and right rows that I talked about so both of them are going to be the same so I'm just going to set them to this make sure you do create a separate Row for each you don't want them both to be the same row like the same reference to the same row so this is how you can do that in Python this is like what the general formula would be let's say for left we're going to go column from left to right we're going to go from one to columns because we're going to do this the value we're going to put at the current column is going to be either itself like the value in the row at that column which we can get from the previous row remember that's how we're Computing this left row so from the previous row at the same column we can get that or we can say what we already have in the left row at index C minus1 so that's why we are starting at column 1 if we started at column zero this would take us out of bounds and python actually wouldn't which is going to be hard to debug so make sure to do this and not only that but the value here we should minus one from it cuz it is at like a differing Row from this column and it's a difference of one so that's why we do that but you might see the problem here we initialize this left row with all zeros but the first value that index zero should have been initialized to what it should have been initialized to the value in the previous row at the same index remember this whole left row is being computed based on the values in this one so here let's do row at index zero we're going to do something very similar um to fill in the right row just going going in the opposite direction in Python you can do that like this for range um at the last index except not the last index column minus one nope instead of doing columnus one we're going to do column minus 2 and we're going to go up until zero so for here we put a negative 1 and then we put a Nega one for the step that means we're decrementing by one each time and then right is going to be column it's going to be the max of itself once again row at that column and right this time it's going to be at right at column + one cuz we're going in the opposite direction remember and here we're still going to put a minus one though now from this you might see that since we're not starting at the last column we should initialize the value at the last column so at right columns minus one should be whatever it was in the previous row at that same index columns minus1 so this is almost the whole code now to actually populate the next row so just like we did we're going to do this you can do it in either direction from left to right or right to left I will do it like this so the value at next row we want to know what we should add to this we already have the original values from the next row but what should we add to it well we want to add to it the maximum of the value from the left and the value from the right at index C so let me make sure to add that there and there so this is pretty much the entire code just don't forget to change the row to the next row before you do the the next iteration of the loop and then at the end we're just going to return the max value in the row so I'm going to go ahead and run this and as you can see it works and it's pretty efficient if you found this helpful check out NE code. for a lot more and hopefully I'll see you soon