发表于 2024.08.07

• 问题I可以直接记忆化搜索/动态规划解决，即遍历所有可能的切法，递归计算各种切法的总开销，取最小值即可。即对于一个初始位置为(begin_r, begin_c)，大小为(width, height)的矩形，最小的开销记为dp(begin_r, begin_c, width, height), 则有如下递归关系：

  1. 如果width == 1或height == 1，则返回0；

  2. 如果height > 1，则可以在height - 1个位置切开，对于每个位置1 <= i < height，计算dp(begin_r, begin_c, width, i) + dp(begin_r, begin_c + i, width, height - i)的最小值；

  3. 如果width > 1，则可以在width - 1个位置切开，对于每个位置1 <= j < width，计算dp(begin_r, begin_c, j, height) + dp(begin_r + j, begin_c, width - j, height)的最小值。

  4. 最终结果即为上述两种情况的最小值。

  问题II由于数据量很大(1 <= m, n <= 10^5)，无法穷举所有的切法，我们需要通过观察下是否可以采取贪心的策略：

  1. 做法1: 不必遍历所有的横切/竖切方法，每个方向只取开销最大的切法即可(否则，如果开销最大的切法放在后面切，因为另一个方向的蛋糕可能会变多，可能会使得开销变大(方向1切法开销 * 方向2切片数量))

  2. 改进做法1: 由于需要找到开销最大的切法，在每一次递归中每个方向都需要遍历一次，重复计算了很多次，不妨使用ST表来预处理每个区间的最大值，这样可以在O(1)时间内找到每个区间的最大值。

  3. 进一步改进：递归的开销同样巨大，由于做法1已经不是穷举所有的切法，可以转为队列的方式，每次取出开销最大的切法，然后将其切开，将新的切法加入队列中，直到队列为空。

  4. 做法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 ans

  3218的做法，直接使用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)

• LC 题目链接