Minimum Cost for Cutting Cake I
01 · Problem
An m x n cake must be cut into m * n pieces of size 1 x 1. You are given:
horizontalCutof lengthm - 1, wherehorizontalCut[i]is the cost of cutting along horizontal linei.verticalCutof lengthn - 1, whereverticalCut[j]is the cost of cutting along vertical linej.
In one step you take any piece that is not yet 1 x 1 and cut it straight across along one of its internal grid lines. Cutting a single piece along line i costs exactly the line's cost, and that cost is not shared: if the same line runs through several separate pieces, each of those pieces must be cut individually and each cut is paid for.
Return the minimum total cost to reduce the whole cake to 1 x 1 pieces. If m == n == 1 the cake needs no cuts and the answer is 0.
02 · Examples
m = 2, n = 3, horizontalCut = [4], verticalCut = [2,6]
18
Cut vertical line 1 first (cost 6), giving two pieces. Cut the horizontal line through both pieces (4 + 4 = 8). Then vertical line 0 runs through two pieces (2 + 2 = 4). Total 6 + 8 + 4 = 18.
m = 1, n = 3, horizontalCut = [], verticalCut = [2,7]
9
There are no horizontal lines. Each vertical line is cut once through the single row: 2 + 7 = 9.
m = 3, n = 3, horizontalCut = [1,3], verticalCut = [5,1]
16
Take the most expensive line first. Vertical line 0 (cost 5) once: 5. Horizontal line 1 (cost 3) through 2 columns: 6. Horizontal line 0 (cost 1) through 2 columns: 2. Vertical line 1 (cost 1) through 3 rows: 3. Total 5 + 6 + 2 + 3 = 16.
03 · Constraints
- 011 <= m, n <= 20
- 02horizontalCut.length == m - 1
- 03verticalCut.length == n - 1
- 041 <= horizontalCut[i], verticalCut[i] <= 1000
04 · Optimal complexity
- Time
- O((m + n) log(m + n))
- Space
- O(m + n)
Practice it alone or rehearse it as an interview.
Practice Mode gives you an editor and test runs, nothing else. AI Interview Mode puts a voice interviewer on the other side, adds a clock, and ends with a scored summary of the round.