What is the primary approach for solving the Minimum Cost for Cutting Cake I problem?

The problem is best solved using dynamic programming with state transitions, ensuring that the cuts are made in the optimal order to minimize cost.

How do I minimize the cost of cutting the cake in this problem?

By sorting both the horizontal and vertical cuts and applying dynamic programming to track the minimum cost, you can achieve the optimal solution.

Why is sorting important in the Minimum Cost for Cutting Cake I problem?

Sorting ensures that cuts are made in the optimal order, with the largest cuts being made first to minimize the total cost.

What is the time complexity of the solution for this problem?

The time complexity is dominated by the sorting of the cuts, which takes O(m log m + n log n), where m and n are the lengths of the horizontal and vertical cuts.

Can this problem be solved using a greedy algorithm?

Yes, a greedy approach is used by making the largest possible cuts first, but dynamic programming is applied to ensure optimal state transitions for cost minimization.

#3218

Medium

auto_awesome状态·转移·动态规划

LeetCode 题解工作台

切蛋糕的最小总开销 I

有一个 m x n 大小的矩形蛋糕，需要切成 1 x 1 的小块。给你整数 m ， n 和两个数组： horizontalCut 的大小为 m - 1 ，其中 horizontalCut[i] 表示沿着水平线 i 切蛋糕的开销。 verticalCut 的大小为 n - 1 ，其中 vertica…

数组动态规划贪心排序

题目描述

有一个 m x n 大小的矩形蛋糕，需要切成 1 x 1 的小块。

给你整数 m ，n 和两个数组：

horizontalCut 的大小为 m - 1 ，其中 horizontalCut[i] 表示沿着水平线 i 切蛋糕的开销。
verticalCut 的大小为 n - 1 ，其中 verticalCut[j] 表示沿着垂直线 j 切蛋糕的开销。

一次操作中，你可以选择任意不是 1 x 1 大小的矩形蛋糕并执行以下操作之一：

沿着水平线 i 切开蛋糕，开销为 horizontalCut[i] 。
沿着垂直线 j 切开蛋糕，开销为 verticalCut[j] 。

每次操作后，这块蛋糕都被切成两个独立的小蛋糕。

每次操作的开销都为最开始对应切割线的开销，并且不会改变。

请你返回将蛋糕全部切成 1 x 1 的蛋糕块的最小总开销。

示例 1：

输入：m = 3, n = 2, horizontalCut = [1,3], verticalCut = [5]

输出：13

解释：

沿着垂直线 0 切开蛋糕，开销为 5 。
沿着水平线 0 切开 3 x 1 的蛋糕块，开销为 1 。
沿着水平线 0 切开 3 x 1 的蛋糕块，开销为 1 。
沿着水平线 1 切开 2 x 1 的蛋糕块，开销为 3 。
沿着水平线 1 切开 2 x 1 的蛋糕块，开销为 3 。

总开销为 5 + 1 + 1 + 3 + 3 = 13 。

示例 2：

输入：m = 2, n = 2, horizontalCut = [7], verticalCut = [4]

输出：15

解释：

沿着水平线 0 切开蛋糕，开销为 7 。
沿着垂直线 0 切开 1 x 2 的蛋糕块，开销为 4 。
沿着垂直线 0 切开 1 x 2 的蛋糕块，开销为 4 。

总开销为 7 + 4 + 4 = 15 。

提示：

1 <= m, n <= 20
horizontalCut.length == m - 1
verticalCut.length == n - 1
1 <= horizontalCut[i], verticalCut[i] <= 10³

lightbulb

解题思路

方法一：贪心 + 双指针

对于一个位置，越早切，所需要切的次数越少，因此，显然是开销越大的位置越早切。

所以，我们可以对数组 $\textit{horizontalCut}$ 和 $\textit{verticalCut}$ 按照从大到小的顺序排序，然后使用两个指针 $i$ 和 $j$ 分别指向 $\textit{horizontalCut}$ 和 $\textit{verticalCut}$ 的开销，每次选择开销较大的位置进行切割，同时更新对应的行数和列数。

每次在水平方向上切割时，如果此前列数为 $v$ ，那么此次的开销为 $\textit{horizontalCut}[i] \times v$ ，然后行数 $h$ 加一；同理，每次在垂直方向上切割时，如果此前行数为 $h$ ，那么此次的开销为 $\textit{verticalCut}[j] \times h$ ，然后列数 $v$ 加一。

最后，当 $i$ 和 $j$ 都到达末尾时，返回总开销即可。

时间复杂度 $O(m \times \log m + n \times \log n)$ ，空间复杂度 $O(\log m + \log n)$ 。其中 $m$ 和 $n$ 分别为 $\textit{horizontalCut}$ 和 $\textit{verticalCut}$ 的长度。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

class Solution:
    def minimumCost(
        self, m: int, n: int, horizontalCut: List[int], verticalCut: List[int]
    ) -> int:
        horizontalCut.sort(reverse=True)
        verticalCut.sort(reverse=True)
        ans = i = j = 0
        h = v = 1
        while i < m - 1 or j < n - 1:
            if j == n - 1 or (i < m - 1 and horizontalCut[i] > verticalCut[j]):
                ans += horizontalCut[i] * v
                h, i = h + 1, i + 1
            else:
                ans += verticalCut[j] * h
                v, j = v + 1, j + 1
        return ans

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Candidate demonstrates understanding of sorting techniques.
question_mark
Candidate can effectively implement dynamic programming for state transitions.
question_mark
Candidate identifies and applies greedy principles to minimize cost.

warning

常见陷阱

外企场景

error
Failing to sort the cuts properly and making cuts in the wrong order.
error
Not understanding how dynamic programming can minimize the cutting cost over multiple steps.
error
Overcomplicating the solution by not leveraging the correct greedy algorithm.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Use a recursive approach to simulate the process instead of dynamic programming.
arrow_right_alt
Optimize the dynamic programming approach for larger inputs.
arrow_right_alt
Explore alternative greedy approaches for different input sizes.

help

常见问题

外企场景

继续练习

#3068 最大节点价值之和 #2708 一个小组的最大实力值 #2616 最小化数对的最大差值