Maximum Score From Grid Operations | LeetCode 3225 - Python

本站添加: 2026-05-06

[00:00:00]Hello everyone. I'm Paul and this is Prolan 3,225 maximum score from grid operations. This is a hard one that's very visual. So next I will show you how to solve this visually and then we will go with the code. We are given a grid of size n * n.

[00:00:17]So let's say that we're given this every cell is white initially and in one operation we can select any cell and color black all the cells in the same column starting from the top row down to the current row. So if we pick this cell we can color black all cells in this column starting from row number zero up to the current row. So in one operation all of this is black now. Now we need to get the maximum possible score that we can achieve after some number of operations. And the way to get the corresponding score is we take the sum of all the values that are right next to some cell that's black in the same row.

[00:01:03]For example, if we're given this example, we can color these cells black.

[00:01:08]We color this black. And the corresponding score is given by the sum of all of these values here. 5 + 3 + 3 is equal to 11. So the result is this.

[00:01:24]The maximum possible score that we can achieve after some number of operations is 11. Let's see this example. And let's say for a moment that we only have one column. So we don't have this. We are looking at this column only. What's the result here? Well, it's zero because the score is the sum of all white cells that are right next to some black cell in the same row. In this row, we have one value. Here we have one value. Here we have one value. So the final result here is zero. Now let's expand this. What if we have two columns? Meaning we don't have this column. If we want to take these three values, we have to paint these three cells. And if we want to take these three values instead, we have to paint these three cells. But there are more possible combinations. What if we are trying to get these two values?

[00:02:19]Well, we should paint these two cells.

[00:02:21]And if we want to take only this value, we should paint this cell. So we should try every possible combination. The question is how can we do this? I like to visualize this as follows. We can have break points which are lines corresponding to the growing color of the shape minus one column. This column on the right corresponds to shade and the previous column is sh minus one. So this line means that we have a growing color on this column that goes from the start up to this row. So the score that we find above the line corresponds to the shade column and the score that we find below the line corresponds to the shade minus one column. So this is the final picture for this breakpoint but we have to explore every possible scenario.

[00:03:13]So what we can do here is grow the shade color from the start one by one. First we are here which means that we are taking this score. Then we grow one cell then we grow another cell. So now we are taking this color in shade minus one which corresponds to the previous column. Then we take another cell and so on. That's how we explore every possible scenario. So if we go from the start this is the break point. First we grow this cell which means that we are taking this value for the previous column. Then we grow another cell in this shade column. Then we grow another cell. The next break point is here which means that we grow one cell in shade minus one. So now this is black and we can do the same. We are growing colors on the shade column one by one. So first we are in this scenario then we grow one color then we grow another one. Then we grow another one. Then we have this break point which means that the two cells are black. And we do the same. We start here. Then we grow this. Then we grow this. Then we grow this. Finally the break point is here which means that all of these is black. And we do the same.

[00:04:31]First we don't grow anything. Then we grow this. Then this. And then this. So we could just try every possible combination in these two columns and keep the maximum possible result. This will be fine for two columns only. But the thing is that we can have more columns. So the key here is that we can solve this sub problem and store the results of this sub problem in this column and then repeat the same process with these two columns and so on until we reach the end of the grid. This is basically dynamic programming. So we will have a DP grid of size n + 1 * n.

[00:05:13]Why? Well, because we can paint zero rows. So we are actually considering this. So this has a size of 3 + 1. For every column, we have two possible scenarios. It's either already used or not used. So let's see what this means.

[00:05:29]Let's say that we have a break point here. So we paint these two cells. And right now we are painting these three cells. So we are deciding if we take this score or not. The key here is that if we take this score, we can't take previous scores in this same column before this break point. For example, let's say that this is larger. And here we have a five. Five is greater than two. But if we take this two, we are not taking the previous five. Why? Well, because the colors grow from row zero every time. So if we want to achieve this scenario where we take number two, we have to grow this color from row zero. This means that we can't have spaces before this. Okay. So we have two possible scenarios. One is we have already used the column meaning we can't take this two because we have already taken some previous white space or this column is available and we can take the current score. So we start from column number one and we are looking at this column and the previous one. So this is sh this is sh minus one and we will do what we did before. This is the initial break point. So what do we have above the line? What's the corresponding score for column number one? Well, it's initially zero. And what's the corresponding score below the line for column zero? We will call this previous.

[00:07:04]This is zero. So this is the current scenario. Now the question is what do we put here in the coordinates corresponding to this cell. Well, first we can take the maximum result of the previous column which is given by the maximum between the scenario in which this column is already taken meaning zero and the scenario in which this column is available and we add the current previous score 0 + 0 is 0 and the maximum between 0 and 0 is equal to zero. So we are standing here. What if we don't take this column? Well, we can take the previous maximum score zero and the maximum between zero and zero is zero. So here we keep zero. And what if we take the current column? Well, we can take the maximum previous score plus the current contribution which is zero. 0 + 0 is 0 which is equal to 0. So here we keep 0 0. Now we can grow this cell which means that current is still zero and previous is now one. So how do we get the maximum score for the previous column? Well, we take the maximum between the scenario in which this column is available plus the current previous 0 + 1 is one. So we take the maximum between one and the scenario in which this column is already used zero.

[00:08:28]The maximum here is one. So what do we put here? Well, if we don't use this column, we need to take the previous maximum one. 1 is greater than zero. So this is one. And if we decide to use this column, we take the previous maximum 1 + 0. 1 + 0 is 1, which is greater than zero. So this is one. Now we can grow another cell. So current is still zero. Previous is now 1 + one meaning two. The maximum previous is given by the scenario in which the column is available plus the current previous. This is two. And the scenario in which the column is already used zero. The result here is two. And here we have to fill the two values. Here we take the maximum between zero and two which is two. And here we take the maximum between zero and 2 + 0 which is two.

[00:09:25]Now we can grow the last cell. So current is zero and previous is 2 + 1 + 1 meaning four. What's the maximum for the previous column? Well, we take the corresponding value for when the column is available plus the current previous 0 + 4 is four. And the scenario in which the column is already used zero. The result here is four. So what do we put here when we don't use this column?

[00:09:56]Well, we take the maximum between zero and the maximum for the previous column.

[00:09:59]So this is four. And if we do use this column, we take the maximum between zero and four + zero. Now we can move the break point and we are still at column one, which means that we are painting this cell. So here current is equal to two and previous is zero. So what's the maximum value for the previous column?

[00:10:24]Well, we can take this cell now because this is the current break point. So, we are looking at these two values here.

[00:10:32]The scenario in which the column is available is zero plus previous the result is zero. And the scenario in which we have already used the column is zero. So, the maximum here is zero. And what do we put at this position? Well, if this column is available, this means that we need to take the maximum previous value, which is zero, and the maximum between 0 and 0 is zero. And if we decide to use the column, we take the maximum previous value plus the current value. And two, the maximum between two and zero is two. Now, we can paint this cell and do the same. Current is zero, previous is zero. So, um, what do we put here? Well, first the maximum result for the previous column is given by the scenario in which the column is available plus previous meaning zero and the scenario in which we use the column is zero. The maximum between 0 and zero is zero. So the maximum previous is zero. And what do we put here? Well, here we keep the maximum between one and the maximum previous meaning zero. And here we keep the maximum between one and the maximum previous meaning 0 plus current. 0 plus 0 is 0 which is more than one. So we keep this. And if we repeat the same process, well next we paint this. So these two values stay the same. Then we paint this. So here we get the same also. The next break point is here which means that we paint these two cells and we do the same. We are painting the cells in column number one one by one. So right now we are at zero meaning here and the previous is initially zero current is the sum of these two values meaning two. So what's the corresponding maximum result for the previous column? Well we can take the maximum between the scenario in which the column is available plus previous and the scenario in which the column is already used. The maximum is zero. So what do we put here? Well, here we keep the maximum between zero and zero. And here we keep the maximum between two and zero plus two, which is two. So we keep two. Next we paint this and these results stay the same. Then we paint this. This stays the same. Finally, we paint this and this stays the same. The final break point is here, which means that we paint this cell here. previous is zero and current is the sum of these values. 2 + 1 is three. So what's the maximum previous value? Well, we can take the maximum value for when the column is available 0 + previous and the maximum value for when we have already used this column zero. The maximum here is zero. So what do we put here? Or here we keep the maximum between zero and the maximum previous value. So this stays at zero. And here we keep the maximum between two and the maximum previous value plus current which is three. Three is greater than two. So we replace this with three. So next we paint this then we paint this then we paint this and that's it. Now we can continue with the next column. These are the final results for column number one. Now we are standing here which means that we are looking at these two columns only. we can forget about column number zero.

[00:14:09]Okay. So we do exactly the same. We start from this break point. Current is zero. Previous is zero. So we take um the maximum value for the previous column first which is given by the maximum between 0 + 0 which is zero and three. The maximum is free. Meaning the best scenario is where we have already used this column. Okay. So the maximum previous is three. What do we put here?

[00:14:38]Well, here we put the maximum between zero and three which is three. And here we put the maximum between zero and three plus current which is three. Now we can grow this cell which means that current is zero, previous is two. So what do we put here? Well, we need to take the maximum value for the previous column first. So we go here and the scenario in which the column is available is zero plus previous we get two. So the maximum between two and three is three. This means that here we need to keep the maximum between zero and three which is three. And here we keep the maximum between zero and three plus zero which is three.

[00:15:24]Next we paint this and get three and three here. Then we paint this and get free and free. So now we can move the break point. Next the break point is here which means that we paint this cell and now we paint every cell at column two one by one. We start from zero then one then two then three and that's it.

[00:15:50]Next we do the same with this break point and then with this break point.

[00:15:54]Finally we get this TP grid where the result is somewhere on this last column here we have the accumulated results. So we need to take the maximum between these scenarios in which we do use the last column because we are trying to get the maximum possible result. The maximum number here is 10. So this is the result. And just to be clear, this means that we can paint these three cells and here 1 + 1 + 2 + 3 + 2 + 1 is equal to 10. Time complexity here is big of n cube. Why? Well, because we are going through these columns one by one and from each of these we have break points.

[00:16:38]We are trying every possible break point and from each break point we are going through every row one by one. So this is n to the^ of 3 and space complexity is big o of n²ar because of this dp grid.

[00:16:56]So with this in mind let's see how to code this up. First n is the length of grid and we can say that if n is equal to one we just return zero. Why? Well because the maximum score for when we only have one cell is zero. Now we need a dp grid. So this is an array which includes an array and every time we have a tpple with 0 0 we want this for every index in range n and we want this for every index in range n.

[00:17:29]Now here I'm missing to add one because remember that in the DP we store counts and well the grid is zero indexed and we need to count the scenario in which we color zero cells from top to bottom. So it's very important to add one here. And now we can say for every column for sh in range and we start from 1 to n every time we go through every possible break point. So for i in range n + one and we can say dp 0 and dp1 are equal to dp i and the corresponding value for the previous column. Okay. So previous is initially zero and current is initially the sum of grid previous shape for every previous in range I. Remember what we are doing here initially the value for current corresponds to the maximum possible score that we can get above the line above the break point. So this is the sum of every value in the grid up to the current index minus one because this is non-inclusive.

[00:18:43]And now we can say for every k in range n + one we are scanning rows from top to bottom considering the current break point. We can say if K is strictly greater than zero and K is smaller or equal to Y. This means that we are in the zone corresponding to the shade column. So we say current minus equal with K minus one shade. Why? Well because remember that current corresponds to the shade column and previous corresponds to the shade minus one column. We are growing colors in the shade column one by one. So if we grow one color we need to subtract the corresponding value from current. Now if K is um strictly greater than I this means that we are in the sum corresponding to the previous column. So we are working with previous. Now here we need to add at K minus one J minus one because this corresponds to the previous column. And here we used k minus one because remember that we are working with counts here but the grid is zero index. So it's very important to subtract one from k. And now we can say that the maximum value for the previous column is the maximum between the scenario in which we have already used that column and the scenario in which the column is available plus previous.

[00:20:17]Remember that this is the current score for previous column. Okay. And now with this we can see that the new value for when the current column the shade column is available is the maximum between what we already have here. This is DP at K shade zero and well here we take the maximum value for the previous column.

[00:20:44]And we can do something very similar for N1. What if we are using the shade column? Well, we can take the maximum between what we already have here and the maximum previous plus current. And now we can say DP at K is equal to a tapole with N0 N1.

[00:21:09]And that's it. Now we can go down here and return the maximum value um in the last column. So we take the maximum of DP and this is I at the last column at index one because we want to consider scenarios in which we have already used this column because we are looking for the maximum possible result.

[00:21:32]So we want this for every index in range n + one. We are going through every row on the last column. So I think this is right. Let's submit this and see if it works. As you can see, this works and it's very efficient. And I'm sure that you can make this even more efficient.

[00:21:53]For example, you replace this with a prefix sum, but I will leave that for you. This is it for this problem. So if you found this useful, please drop a like, subscribe, and see you in the next one. Bye-bye.