<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>

class Solution:
    def maximumScore(self, grid: List[List[int]]) -> int:
        dp = {} # col - 2 height, col - 1 height, col
        n = len(grid)
        vertical_psum = [[0 for c in range(n)] for r in range(n + 1)]
        for r in range(1, n + 1):
            for c in range(n):
                vertical_psum[r][c] = vertical_psum[r - 1][c] + grid[r - 1][c]

        
        def evaluate_column(col_idx, h, h_other):
            if col_idx < 0: return 0
            if h > h_other: return 0
            min_y = h + 1
            max_y = h_other + 1
            col_sum = 0
            col_sum = vertical_psum[max_y][col_idx] - vertical_psum[min_y][col_idx]


            return col_sum
        
        # def evaluate_column_new(col_idx, h, h_other)

        def recurse(colm2_bigger, colm1_height, col_idx):
            # base case
            if col_idx >= n: 
                if colm2_bigger: return 0
                else:
                    return 0
                    # col_value = evaluate_column(col_idx - 1, colm1_height, -1)
                    # return col_value

            key = (colm2_bigger, colm1_height, col_idx)
            if key in dp: return dp[key]

            best_subgrid_value = 0
            for col0_height in range(-1, n):
                m2bigger_col = evaluate_column(col_idx, col0_height, colm1_height)
                m2bigger_child = recurse(True, col0_height, col_idx + 1) + m2bigger_col
                not_m2bigger_child = recurse(False, col0_height, col_idx + 1)


                child_value = max(m2bigger_child, not_m2bigger_child)
                
                col_modifier = 0
                if not colm2_bigger: 
                    col_modifier = evaluate_column(col_idx - 1, colm1_height, col0_height)
                
                # print(colm2_bigger,col_idx, colm1_height, col0_height)
                # print((m2bigger_child, m2bigger_col), not_m2bigger_child, col_modifier)

                child_value += col_modifier
                best_subgrid_value = max(best_subgrid_value, child_value)
            
            dp[key] = best_subgrid_value
            return best_subgrid_value

        dp = [[[0 for i in range(n + 1)] for j in range(n + 1)] for k in [True, False]]
        print(len(dp), len(dp[0]), len(dp[0][0]))
        # for col_idx in [n]:
        #     for colm1_height in range(-1,n):
        #         for colm2_bigger in [True, False]:
        #             # dp[(colm2_bigger, colm1_height, col_idx)] = 0
        #             dp[int(colm2_bigger)][colm1_height][col_idx] = 0

        for col_idx in range(n-1, -1, -1):
            for colm1_height in range(-1, n):
                for colm2_bigger in [True, False]:
                    key = (colm2_bigger, colm1_height, col_idx)
                    best_subgrid_value = 0
                    for col0_height in range(-1, n):
                        m2bigger_col = evaluate_column(col_idx, col0_height, colm1_height)
                        m2bigger_child = dp[1][col0_height][col_idx + 1] + m2bigger_col
                        not_m2bigger_child = dp[0][col0_height][col_idx + 1] 

                        child_value = max(m2bigger_child, not_m2bigger_child)
                        
                        col_modifier = 0
                        if not colm2_bigger: 
                            col_modifier = evaluate_column(col_idx - 1, colm1_height, col0_height)
                        child_value += col_modifier
                        best_subgrid_value = max(best_subgrid_value, child_value)

                    dp[int(colm2_bigger)][colm1_height][col_idx] = best_subgrid_value
                    # print(key, best_subgrid_value)

        return dp[0][-1][0]
        # return recurse(False, -1, 0)


21600