1. 解题思路
这一题是题目3218的进阶版,主要就是增大了 m , n m,n m,n的取值范围,所以直接用上一题的解法的话会出现超时。
不过考虑到体重限定了cost的范围在1000以内,因此我们可以先将cost进行归并,这样就可以化归到上一题的情形进行处理了。
2. 代码实现
给出python代码实现如下:
class Solution:
def minimumCost(self, m: int, n: int, horizontalCut: List[int], verticalCut: List[int]) -> int:
horizontalCut = sorted(Counter(horizontalCut).items(), reverse=True)
verticalCut = sorted(Counter(verticalCut).items(), reverse=True)
@lru_cache(None)
def dp(i, j, rows, cols):
if rows == m:
return sum([cost * num * m for cost, num in verticalCut[j:]])
elif cols == n:
return sum([cost * num * n for cost, num in horizontalCut[i:]])
elif horizontalCut[i][0] > verticalCut[j][0]:
cost, num = horizontalCut[i]
return cost * num * cols + dp(i+1, j, rows+num, cols)
elif horizontalCut[i] < verticalCut[j]:
cost, num = verticalCut[j]
return cost * num * rows + dp(i, j+1, rows, cols+num)
else:
cost, num = horizontalCut[i]
ans1 = cost * num * cols + dp(i+1, j, rows+num, cols)
cost, num = verticalCut[j]
ans2 = cost * num * rows + dp(i, j+1, rows, cols+num)
return min(ans1, ans2)
return dp(0, 0, 1, 1)
提交代码评测得到:耗时1743ms,占用内存39.9MB。