Watch 10 video solutions for Minimum Cost for Cutting Cake I, a medium level problem involving Array, Dynamic Programming, Greedy. This walkthrough by NeetCode has 75,555 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] <= 103