1. 解题思路
这一题放弃了，太繁琐了，直接抄了其他大佬的答案。
思路上的话其实我们是一样的，都是一步步拆分，对于一个矩形的情况，就退化到前面题目3195的情况，没啥好多说的。
然后对于两个的情况，必然是上下结构或者左右结构的两个矩形，因此又可以化作上述一个矩形的情况。
然后，对于3个矩形的情况，又可以拆分为上下结构和左右结构，然后分别是一边一个，一边两个矩形，然后就又退化到了上述一和二中的两种情况。
我们对其进行一下实现即可，但是委实有点烦，写了半天没写对，然后看了一下其他大佬们的解答，思路是一样的，所以就偷个懒了，直接找大佬们的答案吧……
2. 代码实现
给出python实现如下：
class Solution:
def minimumSum(self, grid: List[List[int]]) -> int:
@lru_cache
def solve1(i1, i2, j1, j2):
imin = jmin = inf
imax = jmax = -1
for i in range(i1, i2):
for j in range(j1, j2):
if grid[i][j]:
imin = min(imin, i)
imax = max(imax, i)
jmin = min(jmin, j)
jmax = max(jmax, j)
if imax == -1:
return 0
return (imax - imin + 1) * (jmax - jmin + 1)
def solve2(i1, i2, j1, j2):
ans = inf
for i in range(i1+1, i2):
ans = min(ans, solve1(i1, i, j1, j2) + solve1(i, i2, j1, j2))
for j in range(j1+1, j2):
ans = min(ans, solve1(i1, i2, j1, j) + solve1(i1, i2, j, j2))
return ans
def solve3(i1, i2, j1, j2):
ans = inf
for i in range(i1+1, i2):
ans = min(ans, solve2(i1, i, j1, j2) + solve1(i, i2, j1, j2))
ans = min(ans, solve1(i1, i, j1, j2) + solve2(i, i2, j1, j2))
for j in range(j1+1, j2):
ans = min(ans, solve2(i1, i2, j1, j) + solve1(i1, i2, j, j2))
ans = min(ans, solve1(i1, i2, j1, j) + solve2(i1, i2, j, j2))
return ans
return solve3(0, len(grid), 0, len(grid[0]))
提交代码评测得到：耗时3981ms，占用内存16.6MB。