<p>You are given a 2D matrix <code>grid</code> of size <code>n x n</code>. Initially, all cells of the grid are colored white. In one operation, you can select any cell of indices <code>(i, j)</code>, and color black all the cells of the <code>j<sup>th</sup></code> column starting from the top row down to the <code>i<sup>th</sup></code> row.</p>

<p>The grid score is the sum of all <code>grid[i][j]</code> such that cell <code>(i, j)</code> is white and it has a horizontally adjacent black cell.</p>

<p>Return the <strong>maximum</strong> score that can be achieved after some number of operations.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">grid = [[0,0,0,0,0],[0,0,3,0,0],[0,1,0,0,0],[5,0,0,3,0],[0,0,0,0,2]]</span></p>

<p><strong>Output:</strong> <span class="example-io">11</span></p>

<p><strong>Explanation:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2024/05/11/one.png" style="width: 300px; height: 200px;" />
<p>In the first operation, we color all cells in column 1 down to row 3, and in the second operation, we color all cells in column 4 down to the last row. The score of the resulting grid is <code>grid[3][0] + grid[1][2] + grid[3][3]</code> which is equal to 11.</p>
</div>

<p><strong class="example">Example 2:</strong></p>

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">grid = [[10,9,0,0,15],[7,1,0,8,0],[5,20,0,11,0],[0,0,0,1,2],[8,12,1,10,3]]</span></p>

<p><strong>Output:</strong> <span class="example-io">94</span></p>

<p><strong>Explanation:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2024/05/11/two-1.png" style="width: 300px; height: 200px;" />
<p>We perform operations on 1, 2, and 3 down to rows 1, 4, and 0, respectively. The score of the resulting grid is <code>grid[0][0] + grid[1][0] + grid[2][1] + grid[4][1] + grid[1][3] + grid[2][3] + grid[3][3] + grid[4][3] + grid[0][4]</code> which is equal to 94.</p>
</div>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;=&nbsp;n == grid.length &lt;= 100</code></li>
	<li><code>n == grid[i].length</code></li>
	<li><code>0 &lt;= grid[i][j] &lt;= 10<sup>9</sup></code></li>
</ul>

from functools import cache
class Solution:
    def maximumScore(self, grid: List[List[int]]) -> int:
        '''
        Solution needs to be O(N^3)
        '''

        m, n = len(grid), len(grid[0])
        prefixes = [[0 for _ in range(n)] for j in range(m+1)]
        for j in range(n):
            for i in range(1, m+1):
                prefixes[i][j] = prefixes[i-1][j] + grid[i-1][j]

        dp = [[[0 for _ in range(n+1)] for _ in range(m+1)] for _ in range(2)]
        for col_idx in range(n-1, -1, -1):
            for prev_height in range(0, m+1):
                for is_bigger in range(2):
                    best = 0
                    for height in range(0, m+1):
                        prev_col = 0 if is_bigger else \
                                (prefixes[height][col_idx-1] - prefixes[prev_height][col_idx-1]) if height > prev_height else 0
                        curr_col = (prefixes[prev_height][col_idx] - prefixes[height][col_idx]) if prev_height > height else 0

                        with_bigger = prev_col+curr_col + dp[1][height][col_idx+1]
                        without_bigger = prev_col + dp[0][height][col_idx+1]
                        best = max(best, max(without_bigger, with_bigger))
                        dp[is_bigger][prev_height][col_idx] = best
        return dp[1][0][0]


        # @cache
        # def recurse(is_bigger, p_height, curr_idx):
        #     if curr_idx == n:
        #         return 0
        #     best = 0
        #     for i in range(0, m+1):
        #         prev_col = 0 if is_bigger else (prefixes[i][curr_idx-1] - prefixes[p_height][curr_idx-1]) if i > p_height else 0
        #         curr_col = (prefixes[p_height][curr_idx] - prefixes[i][curr_idx]) if p_height > i else 0

        #         with_bigger = prev_col + curr_col + recurse(True, i, curr_idx+1)
        #         without_bigger = prev_col + recurse(False, i, curr_idx+1)
        #         best = max(best, max(with_bigger, without_bigger))
        #     return best
    
        return recurse(True, 0, 0)
        

        
19300