Watch 9 video solutions for Minimum Cost for Cutting Cake I, a medium level problem involving Array, Dynamic Programming, Greedy. This walkthrough by codestorywithMIK has 5,654 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
There is an m x n cake that needs to be cut into 1 x 1 pieces.
You are given integers m, n, and two arrays:
horizontalCut of size m - 1, where horizontalCut[i] represents the cost to cut along the horizontal line i.verticalCut of size n - 1, where verticalCut[j] represents the cost to cut along the vertical line j.In one operation, you can choose any piece of cake that is not yet a 1 x 1 square and perform one of the following cuts:
i at a cost of horizontalCut[i].j at a cost of verticalCut[j].After the cut, the piece of cake is divided into two distinct pieces.
The cost of a cut depends only on the initial cost of the line and does not change.
Return the minimum total cost to cut the entire cake into 1 x 1 pieces.
Example 1:
Input: m = 3, n = 2, horizontalCut = [1,3], verticalCut = [5]
Output: 13
Explanation:
3 x 1 subgrid with cost 1.3 x 1 subgrid with cost 1.2 x 1 subgrid with cost 3.2 x 1 subgrid with cost 3.The total cost is 5 + 1 + 1 + 3 + 3 = 13.
Example 2:
Input: m = 2, n = 2, horizontalCut = [7], verticalCut = [4]
Output: 15
Explanation:
1 x 2 subgrid with cost 4.1 x 2 subgrid with cost 4.The total cost is 7 + 4 + 4 = 15.
Constraints:
1 <= m, n <= 20horizontalCut.length == m - 1verticalCut.length == n - 11 <= horizontalCut[i], verticalCut[i] <= 103Problem Overview: You are given the costs of horizontal and vertical cuts needed to divide an m x n cake into 1x1 pieces. Each time you perform a cut, the cost is multiplied by the number of current segments in the opposite direction. The goal is to choose the order of cuts so the total cost is minimized.
Approach 1: Greedy with Priority Queue (O((m+n) log(m+n)) time, O(m+n) space)
The key observation: expensive cuts should be applied as early as possible. When you perform a cut later, it gets multiplied by more segments, which increases its total cost. To minimize the final sum, always perform the highest-cost cut first. Push all horizontal and vertical cuts into a max heap (priority queue) and repeatedly extract the largest cost. Maintain counters for horizontal and vertical segments. A horizontal cut contributes cost * verticalSegments, while a vertical cut contributes cost * horizontalSegments. This greedy strategy guarantees the minimum cost because it prevents expensive cuts from being multiplied by larger segment counts later.
This approach relies heavily on ideas from Greedy algorithms and works well because the cost contribution grows multiplicatively as segments increase.
Approach 2: Greedy with Sorting (O((m+n) log(m+n)) time, O(1) extra space)
Instead of using a heap, you can sort both cost arrays in descending order and simulate the greedy selection using two pointers. Compare the next largest horizontal and vertical cost and pick the larger one. Update the segment counters accordingly and accumulate the weighted cost. Sorting allows you to process cuts in decreasing order without maintaining a heap, making the implementation simpler while keeping the same asymptotic complexity.
This version primarily uses Array manipulation and Sorting. In practice it runs slightly faster due to lower constant factors compared to a priority queue.
Approach 3: Dynamic Programming (O(h * v) time, O(h * v) space)
A Dynamic Programming formulation considers how many horizontal and vertical cuts have already been performed. Let dp[i][j] represent the minimum cost after performing i horizontal and j vertical cuts. The next operation can either be another horizontal cut or a vertical cut. A horizontal cut adds horizontalCost[i] * (j + 1), while a vertical cut adds verticalCost[j] * (i + 1). Transition between states until all cuts are used. This explicitly explores interleavings of cut orders but is slower and uses more memory than the greedy strategy.
Recommended for interviews: The greedy strategy with sorting or a priority queue is the expected solution. It demonstrates the core insight: performing higher-cost cuts earlier prevents them from being multiplied by larger segment counts. Mentioning the DP formulation shows deeper understanding, but implementing the greedy approach efficiently is what interviewers typically look for.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Greedy with Priority Queue | O((m+n) log(m+n)) | O(m+n) | When you want a straightforward greedy implementation that always selects the largest remaining cut. |
| Greedy with Sorting | O((m+n) log(m+n)) | O(1) | Most common interview solution; simpler and faster than heap-based implementation. |
| Dynamic Programming | O(h * v) | O(h * v) | Useful for understanding all possible cut orders or when demonstrating DP reasoning. |