<p>You are given a 2D <strong>binary</strong> array <code>grid</code>. You need to find 3 <strong>non-overlapping</strong> rectangles having <strong>non-zero</strong> areas with horizontal and vertical sides such that all the 1&#39;s in <code>grid</code> lie inside these rectangles.</p>

<p>Return the <strong>minimum</strong> possible sum of the area of these rectangles.</p>

<p><strong>Note</strong> that the rectangles are allowed to touch.</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 = [[1,0,1],[1,1,1]]</span></p>

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

<p><strong>Explanation:</strong></p>

<p><img alt="" src="https://assets.leetcode.com/uploads/2024/05/14/example0rect21.png" style="padding: 10px; background: rgb(255, 255, 255); border-radius: 0.5rem; width: 280px; height: 198px;" /></p>

<ul>
	<li>The 1&#39;s at <code>(0, 0)</code> and <code>(1, 0)</code> are covered by a rectangle of area 2.</li>
	<li>The 1&#39;s at <code>(0, 2)</code> and <code>(1, 2)</code> are covered by a rectangle of area 2.</li>
	<li>The 1 at <code>(1, 1)</code> is covered by a rectangle of area 1.</li>
</ul>
</div>

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

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

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

<p><strong>Explanation:</strong></p>

<p><img alt="" src="https://assets.leetcode.com/uploads/2024/05/14/example1rect2.png" style="padding: 10px; background: rgb(255, 255, 255); border-radius: 0.5rem; width: 356px; height: 198px;" /></p>

<ul>
	<li>The 1&#39;s at <code>(0, 0)</code> and <code>(0, 2)</code> are covered by a rectangle of area 3.</li>
	<li>The 1 at <code>(1, 1)</code> is covered by a rectangle of area 1.</li>
	<li>The 1 at <code>(1, 3)</code> is covered by a rectangle of area 1.</li>
</ul>
</div>

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

<ul>
	<li><code>1 &lt;= grid.length, grid[i].length &lt;= 30</code></li>
	<li><code>grid[i][j]</code> is either 0 or 1.</li>
	<li>The input is generated such that there are at least three 1&#39;s in <code>grid</code>.</li>
</ul>

class Solution:
    def minimumSum(self, grid: List[List[int]]) -> int:
        #find every one, then merge boxes until we have only 3 left?
        #First get all the 1s, then merge the adjacent boxes?
        #Cover with 1, then 2, then 3?
        #Bruh literally brute force
        d = dict()
        def getmin(x1, y1, x2, y2):
            #This will return the minimum rectangle that contains all ones
            minx = miny = 31
            maxx = maxy = -1
            for i in range(x1, x2+1):
                for j in range(y1, y2+1):
                    if grid[i][j] == 1:
                        minx = min(minx, i)
                        miny = min(miny, j)
                        maxx = max(maxx, i)
                        maxy = max(maxy, j)
            if minx == 31: return 0
            return (maxx - minx + 1)*(maxy - miny + 1)
        def recurse(x1,y1,x2,y2,num):
            #We will use this to loop through and build up the number of squares
            #Memoization since we will go through the same operations many times
            cur = (x1, y1, x2, y2, num)
            if cur in d:
                return d[cur]
            ans = sys.maxsize
            #if we only need 1 square, just call the func
            if num == 1:
                ans = getmin(x1,y1,x2,y2)
            #If we need 2 sqares, we will divide the grid into 2 rectangles either vertically or horizontally and then recurse, and add those two
            elif num == 2:
                for i in range(x1, x2):
                    ans = min(ans, recurse(x1,y1,i,y2,1) + recurse(i+1,y1,x2,y2,1))
                for j in range(y1, y2):
                    ans = min(ans, recurse(x1,y1,x2,j,1) + recurse(x1,j+1,x2,y2,1))
            #If we need 3 squares, we will simply split the sqaure into 2 again and then run the n=2 algo on both the top and bottom (or l/r) squares
            elif num == 3:
                for i in range(x1,x2):
                    ans = min(ans, recurse(x1,y1,i,y2,2) + recurse(i+1,y1,x2,y2,1))
                    ans = min(ans, recurse(x1,y1,i,y2,1) + recurse(i+1,y1,x2,y2,2))
                for j in range(y1, y2):
                    ans = min(ans, recurse(x1,y1,x2,j,2) + recurse(x1,j+1,x2,y2,1))
                    ans = min(ans, recurse(x1,y1,x2,j,1) + recurse(x1,j+1,x2,y2,2))
            d[cur] = ans
            return ans
            
        sol = recurse(0,0,len(grid)-1,len(grid[0])-1, 3)
        return sol
2076