# Minimum Cost for Cutting Cake I
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/minimum-cost-for-cutting-cake-i)
Canonical: https://scaleengineer.com/dsa/problems/minimum-cost-for-cutting-cake-i
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming), [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array
---
## Problem
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:

1. Cut along a horizontal line `i` at a cost of `horizontalCut[i]`.
2. Cut along a vertical line `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:**

![](https://assets.glich.co/dsa/minimum-cost-for-cutting-cake-i/image0.gif)

* Perform a cut on the vertical line 0 with cost 5, current total cost is 5.
* Perform a cut on the horizontal line 0 on `3 x 1` subgrid with cost 1.
* Perform a cut on the horizontal line 0 on `3 x 1` subgrid with cost 1.
* Perform a cut on the horizontal line 1 on `2 x 1` subgrid with cost 3.
* Perform a cut on the horizontal line 1 on `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:**

* Perform a cut on the horizontal line 0 with cost 7.
* Perform a cut on the vertical line 0 on `1 x 2` subgrid with cost 4.
* Perform a cut on the vertical line 0 on `1 x 2` subgrid with cost 4.

The total cost is `7 + 4 + 4 = 15`.

**Constraints:**

* `1 <= m, n <= 20`
* `horizontalCut.length == m - 1`
* `verticalCut.length == n - 1`
* `1 <= horizontalCut[i], verticalCut[i] <= 103`

# Approaches
## Recursive Approach with Memoization (TLE)
This approach attempts to solve the problem by exploring all possible sequences of cuts. A recursive function is defined to calculate the minimum cost from a given state, where the state is defined by which cuts have already been performed. To optimize the plain recursion, memoization (a top-down dynamic programming technique) is used to store and reuse the results of subproblems that have already been solved.
**Time:** O((m+n) * 2^(m+n)). There are `2^(m+n-2)` states, and for each state, we iterate through up to `m+n-2` possible cuts. · **Space:** O(2^(m+n)). The memoization table would have `2^(m-1) * 2^(n-1)` states. This is infeasible for the given constraints.
**Pros:** It is a systematic way to explore the entire search space, guaranteeing an optimal solution if it runs to completion.; The logic is a direct translation of the problem definition into a recursive structure.
**Cons:** The time complexity is exponential, making it too slow for the given constraints.; The space complexity is also exponential due to the memoization table, which is not feasible for the given constraints.
### Explanation
The state of our recursive function can be defined by the set of cuts that have already been made. We can use two integer bitmasks, `hMask` and `vMask`, to keep track of the horizontal and vertical cuts performed. `solve(hMask, vMask)` would then compute the minimum additional cost to cut the cake completely, given the cuts represented by the masks have been made.

The number of horizontal pieces is `Integer.bitCount(hMask) + 1`, and the number of vertical pieces is `Integer.bitCount(vMask) + 1`. When we decide to make a new horizontal cut `i`, its cost will be `horizontalCut[i]` multiplied by the current number of vertical pieces. Similarly, a new vertical cut `j` costs `verticalCut[j]` multiplied by the current number of horizontal pieces.

The recursion explores every possible next cut, adds its cost to the result of the subsequent recursive call, and finds the minimum among all choices. However, with `m, n <= 20`, the number of states `(2^(m-1) * 2^(n-1))` is prohibitively large, leading to a Time Limit Exceeded (TLE) error.

```java
// This is a conceptual implementation and will result in Time Limit Exceeded.
class Solution {
    long[][] memo;
    int m, n;
    int[] horizontalCut, verticalCut;

    public long minimumCost(int m, int n, int[] horizontalCut, int[] verticalCut) {
        this.m = m;
        this.n = n;
        this.horizontalCut = horizontalCut;
        this.verticalCut = verticalCut;
        // The state space 2^(m-1) * 2^(n-1) is too large for the given constraints.
        // For example, if m=20, n=20, we'd need a memo table of size 2^19 * 2^19.
        // This code is for demonstration of the concept.
        // memo = new long[1 << (m - 1)][1 << (n - 1)];
        // for (long[] row : memo) Arrays.fill(row, -1);
        return solve(0, 0);
    }

    private long solve(int hMask, int vMask) {
        if (hMask == (1 << (m - 1)) - 1 && vMask == (1 << (n - 1)) - 1) {
            return 0;
        }

        // if (memo[hMask][vMask] != -1) return memo[hMask][vMask];

        long minCost = Long.MAX_VALUE;
        int hPieces = Integer.bitCount(hMask) + 1;
        int vPieces = Integer.bitCount(vMask) + 1;

        // Try making an unmade horizontal cut
        for (int i = 0; i < m - 1; i++) {
            if ((hMask & (1 << i)) == 0) {
                long currentCost = (long) horizontalCut[i] * vPieces;
                minCost = Math.min(minCost, currentCost + solve(hMask | (1 << i), vMask));
            }
        }

        // Try making an unmade vertical cut
        for (int j = 0; j < n - 1; j++) {
            if ((vMask & (1 << j)) == 0) {
                long currentCost = (long) verticalCut[j] * hPieces;
                minCost = Math.min(minCost, currentCost + solve(hMask, vMask | (1 << j)));
            }
        }

        // return memo[hMask][vMask] = minCost;
        return minCost;
    }
}
```
### Algorithm
- Define a recursive function, say `solve(hMask, vMask)`, where `hMask` and `vMask` are bitmasks representing the horizontal and vertical cuts that have already been made.
- The base case for the recursion is when all cuts are made (i.e., all bits in `hMask` and `vMask` are set). In this case, the cost is 0.
- In the recursive step, calculate the current number of horizontal pieces (`hPieces = popcount(hMask) + 1`) and vertical pieces (`vPieces = popcount(vMask) + 1`).
- Iterate through all possible next cuts (both horizontal and vertical) that haven't been made yet.
- For each available horizontal cut `i`, calculate the cost as `horizontalCut[i] * vPieces` and recursively call `solve` with the updated `hMask`. 
- For each available vertical cut `j`, calculate the cost as `verticalCut[j] * hPieces` and recursively call `solve` with the updated `vMask`.
- The function returns the minimum cost found among all possible next cuts.
- Use a 2D array for memoization, `memo[hMask][vMask]`, to store the results of subproblems and avoid redundant calculations.

## Greedy Approach
A greedy approach provides an efficient and optimal solution. The main idea is that to minimize the total cost, we should prioritize making cuts with higher costs. The cost of a cut is its base value multiplied by the number of pieces it divides. By making expensive cuts early, when the cake is in fewer pieces, we minimize their contribution to the total cost. This suggests processing all cuts (both horizontal and vertical) in descending order of their costs.
**Time:** O(m log m + n log n). The dominant operation is sorting the two arrays of cut costs. The subsequent two-pointer traversal takes O(m + n) time. · **Space:** O(m + n). This is for storing the `Integer` arrays for sorting. If we sort the primitive arrays and use a custom comparator or sort in ascending and iterate backwards, we can reduce auxiliary space, but `O(m+n)` is a reasonable upper bound for this implementation.
**Pros:** Highly efficient with a polynomial time complexity.; Simple to implement once the greedy strategy is understood.; Guaranteed to find the optimal solution.
**Cons:** The greedy choice is not immediately obvious and its correctness requires a proof (e.g., using an exchange argument).
### Explanation
This greedy strategy can be proven correct using an exchange argument. Assume there is an optimal sequence of cuts where a cut `c1` is performed before a cut `c2`, but `cost(c1) < cost(c2)`. By swapping their order, we can show that the total cost either decreases or stays the same. This implies that an optimal sequence must have cuts sorted in descending order of cost.

To implement this, we can sort both the horizontal and vertical cut costs in descending order. Then, we can use a two-pointer technique to iterate through them, always picking the cut with the higher cost from the two arrays. We maintain a count of the number of horizontal and vertical pieces. When we make a horizontal cut, its cost is multiplied by the current number of vertical pieces. When we make a vertical cut, its cost is multiplied by the current number of horizontal pieces.

```java
import java.util.Arrays;
import java.util.Collections;

class Solution {
    public long minimumCost(int m, int n, int[] horizontalCut, int[] verticalCut) {
        // To sort in descending order, we can use Integer arrays.
        Integer[] hCut = Arrays.stream(horizontalCut).boxed().toArray(Integer[]::new);
        Integer[] vCut = Arrays.stream(verticalCut).boxed().toArray(Integer[]::new);

        Arrays.sort(hCut, Collections.reverseOrder());
        Arrays.sort(vCut, Collections.reverseOrder());

        long totalCost = 0;
        int hPieces = 1;
        int vPieces = 1;
        int i = 0; // pointer for horizontal cuts
        int j = 0; // pointer for vertical cuts

        while (i < hCut.length || j < vCut.length) {
            long hCost = (i < hCut.length) ? hCut[i] : -1;
            long vCost = (j < vCut.length) ? vCut[j] : -1;

            // Greedily pick the more expensive cut.
            if (hCost > vCost) {
                // Make a horizontal cut.
                totalCost += hCost * vPieces;
                hPieces++;
                i++;
            } else {
                // Make a vertical cut.
                totalCost += vCost * hPieces;
                vPieces++;
                j++;
            }
        }
        return totalCost;
    }
}
```
### Algorithm
- The key insight is that it is always optimal to perform the cut with the highest cost first.
- Sort both `horizontalCut` and `verticalCut` arrays in descending order.
- Initialize `hPieces = 1`, `vPieces = 1` (representing one initial cake piece), and `totalCost = 0`.
- Use two pointers, `i` for the sorted horizontal cuts and `j` for the sorted vertical cuts.
- In a loop, compare the costs of the current pointed-to horizontal and vertical cuts (`horizontalCut[i]` and `verticalCut[j]`).
- If the horizontal cut has a higher cost, add `horizontalCut[i] * vPieces` to `totalCost`, increment `hPieces`, and move the horizontal pointer `i`.
- Otherwise, the vertical cut has a higher or equal cost. Add `verticalCut[j] * hPieces` to `totalCost`, increment `vPieces`, and move the vertical pointer `j`.
- Continue until all cuts have been processed. The final `totalCost` is the minimum possible cost.

# Solutions
### Java

```java
class Solution {
public
  int minimumCost(int m, int n, int[] horizontalCut, int[] verticalCut) {
    Arrays.sort(horizontalCut);
    Arrays.sort(verticalCut);
    int ans = 0;
    int i = m - 2, j = n - 2;
    int h = 1, v = 1;
    while (i >= 0 || j >= 0) {
      if (j < 0 || (i >= 0 && horizontalCut[i] > verticalCut[j])) {
        ans += horizontalCut[i--] * v;
        ++h;
      } else {
        ans += verticalCut[j--] * h;
        ++v;
      }
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int minimumCost(int m, int n, vector<int> &horizontalCut,
                  vector<int> &verticalCut) {
    sort(horizontalCut.rbegin(), horizontalCut.rend());
    sort(verticalCut.rbegin(), verticalCut.rend());
    int ans = 0;
    int i = 0, j = 0;
    int h = 1, v = 1;
    while (i < m - 1 || j < n - 1) {
      if (j == n - 1 || (i < m - 1 && horizontalCut[i] > verticalCut[j])) {
        ans += horizontalCut[i++] * v;
        h++;
      } else {
        ans += verticalCut[j++] * h;
        v++;
      }
    }
    return ans;
  }
};

```

### Python

```python
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

```