Leetcode 3225. Maximum Score From Grid Operations

Choose, for each column, a prefix length of rows to color black (turning rows 0..i black in that column); a white cell (i,j) contributes grid[i][j] to the score iff at least one horizontally adjacent cell (i,j-1) or (i,j+1) is black. Maximize the total sum over all cells by selecting the per-column cut heights (n ≤ 100, cell values up to 1e9), which couples decisions across adjacent columns at each row.