<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 typing import Tuple

class Solution:
    def maximumScore(self, grid: List[List[int]]) -> int:
        row_cnt = len(grid)
        col_cnt = len(grid[0])
        self.max_score = 0
        self.prefix_sum_by_col = [[0] * (row_cnt + 1) for _ in range(col_cnt)]

        for col in range(col_cnt):
            for row_selected in range(1, row_cnt + 1):
                self.prefix_sum_by_col[col][row_selected] = grid[row_selected - 1][col] + self.prefix_sum_by_col[col][row_selected - 1]

        # brute force solution
        # memo 
        @lru_cache(maxsize = None)
        def getMaximumScore(cur_col, cur_black_rows_cnt) -> Tuple[int, int]:
            # get the maximum score if we can only use the cols from 0 to cur_col 
            # and the first cur_black_rows_cnt row of the current col are black 
            # return the (maximum score if include cur_col, maximum score if exclude cur_col) pair

            if cur_col <= 0:
                # for the first 1 col, if don't consider the cols afterwards we can never include score
                return 0, 0
            
            prev_col = cur_col - 1
            max_score_including_self, max_score_excluding_self = 0, 0
            for prev_black_rows_cnt in range(row_cnt + 1):
                # include contributions from cur_col 
                # if there is some row we could include for cur_col according to the prev blacks
                cur_col_contributions = 0
                if cur_black_rows_cnt < prev_black_rows_cnt:
                    cur_col_contributions = self.prefix_sum_by_col[cur_col][prev_black_rows_cnt] - self.prefix_sum_by_col[cur_col][cur_black_rows_cnt]
                    # for row in range(cur_black_rows_cnt, prev_black_rows_cnt):
                    #     cur_col_contributions += grid[row][cur_col]
                
                # include contributions from prev_col = cur_col - 1
                max_prev_col_contributions_including_itself = 0
                max_prev_col_contributions_excluding_itself = 0
                max_prev_col_contributions = 0
                max_prev_col_contributions_including_itself, \
                    max_prev_col_contributions_excluding_itself = getMaximumScore(prev_col, prev_black_rows_cnt)
                if cur_black_rows_cnt > prev_black_rows_cnt:
                    max_prev_col_contributions_excluding_itself += self.prefix_sum_by_col[prev_col][cur_black_rows_cnt] - self.prefix_sum_by_col[prev_col][prev_black_rows_cnt]
                    # for row in range(prev_black_rows_cnt, cur_black_rows_cnt):
                    #     max_prev_col_contributions_excluding_itself += grid[row][prev_col]
                max_prev_col_contributions = max(max_prev_col_contributions_excluding_itself, max_prev_col_contributions_including_itself)
                
                max_score_including_self = max(max_score_including_self, cur_col_contributions + max_prev_col_contributions)
                max_score_excluding_self = max(max_score_excluding_self, max_prev_col_contributions)
            
            self.max_score = max(self.max_score, max_score_including_self)
            return max_score_including_self, max_score_excluding_self

        for col in range(col_cnt):
            for black_rows_cnt in range(row_cnt + 1):
                getMaximumScore(col, black_rows_cnt)
            
        return self.max_score
49100