JZX轻语：简
LeetCode 3218 & 3219 - 切蛋糕的最小总开销
发表于2024年08月07日
问题I可以直接记忆化搜索/动态规划解决，即遍历所有可能的切法，递归计算各种切法的总开销，取最小值即可。即对于一个初始位置为(begin_r, begin_c)，大小为(width, height)的矩形，最小的开销记为dp(begin_r, begin_c, width, height), 则有如下递归关系：
如果
width == 1或height == 1，则返回0；如果
height > 1，则可以在height - 1个位置切开，对于每个位置1 <= i < height，计算dp(begin_r, begin_c, width, i) + dp(begin_r, begin_c + i, width, height - i)的最小值；如果
width > 1，则可以在width - 1个位置切开，对于每个位置1 <= j < width，计算dp(begin_r, begin_c, j, height) + dp(begin_r + j, begin_c, width - j, height)的最小值。最终结果即为上述两种情况的最小值。
问题II由于数据量很大(1 <= m, n <= 10^5)，无法穷举所有的切法，我们需要通过观察下是否可以采取贪心的策略：
做法1: 不必遍历所有的横切/竖切方法，每个方向只取开销最大的切法即可(否则，如果开销最大的切法放在后面切，因为另一个方向的蛋糕可能会变多，可能会使得开销变大(
方向1切法开销 * 方向2切片数量))改进做法1: 由于需要找到开销最大的切法，在每一次递归中每个方向都需要遍历一次，重复计算了很多次，不妨使用ST表来预处理每个区间的最大值，这样可以在
O(1)时间内找到每个区间的最大值。进一步改进：递归的开销同样巨大，由于做法1已经不是穷举所有的切法，可以转为队列的方式，每次取出开销最大的切法，然后将其切开，将新的切法加入队列中，直到队列为空。
做法2: 上述做法还是会超时…不妨进一步将贪心用到极致，结合归并的思想：首先对两种切法的开销进行排序，然后候选的切法为开销最大的横切、竖切，然后评估上述两种切法中，能够使得开销最小的切法，重复上述过程，直到候选切法为空。详细的贪心做法见详情。
该题目的贪心做法可行性可使用交换论证法证明。我们将蛋糕的切法看成一个序列，如横, 竖, 横, 竖, 竖, 横...，我们可以发现，对于一个切法序列，如果相邻的两个切法方向相同，那么交换这两个切法总开销不变(因为另一个方向的次数数量不变)。如果相邻的两个切法不同，则记此前横切的次数为cut_h，竖切的次数为cut_v，而这两个切法中，横切的开销为cost_h，竖切的开销为cost_v，如果相邻的切法中，将横切放在前面做，则这两次的开销为cost_h * cut_v + cost_v * (cut_h + 1)，如果将竖切放在前面做，则这两次的开销为cost_v * cut_h + cost_h * (cut_v + 1)，我们可以发现，如果cost_h * cut_v + cost_v * (cut_h + 1) >= cost_v * cut_h + cost_h * (cut_v + 1)，则将横切放在前面做，否则将竖切放在前面做。如此以来，我们可以根据上述特性找到一个最优的切法序列：每次取出横切和竖切中开销最大的切法，然后根据上述规则判断，取出最优的切法，如此循环直到切法序列为空。
3219的做法：
class Solution:
def minimumCost(self, m: int, n: int, horizontalCut: List[int], verticalCut: List[int]) -> int:
# 对两个方向的切法开销进行排序
horizontalCut.sort()
verticalCut.sort()
# 当前横竖切了几块
cut_h = 1
cut_v = 1
ans = 0
while cut_h < m or cut_v < n:
if not horizontalCut: # 只能竖切
ans += verticalCut[-1] * cut_h
verticalCut.pop()
cut_v += 1
elif not verticalCut: # 只能横切
ans += horizontalCut[-1] * cut_v
horizontalCut.pop()
cut_h += 1
else:
# 计算横切和竖切产生的开销
cand_v = horizontalCut[-1] * (cut_v + 1) + verticalCut[-1] * cut_h
cand_h = verticalCut[-1] * (cut_h + 1) + horizontalCut[-1] * cut_v
if cand_v >= cand_v:
ans += horizontalCut[-1] * cand_h
horizontalCut.pop()
cut_h += 1
else:
ans += verticalCut[-1] * cut_h
verticalCut.pop()
cut_v += 1
return ans3218的做法，直接使用dp就能过:
class Solution:
def minimumCost(self, m: int, n: int, horizontalCut: List[int], verticalCut: List[int]) -> int:
@lru_cache(None)
def dp(begin_r: int, begin_c: int, width: int, height: int):
ans = math.inf
if width == height == 1:
return 0
# 横切
if height > 1:
ans = min(ans, min(dp(begin_r, begin_c, width, i) + dp(begin_r + i, begin_c, width, height - i) + horizontalCut[begin_r + i - 1] for i in range(1, height)))
# 竖切
if width > 1:
ans = min(ans, min(dp(begin_r, begin_c, i, height) + dp(begin_r, begin_c + i, width - i, height) + verticalCut[begin_c + i - 1] for i in range(1, width)))
return ans
return dp(0, 0, n, m)