# Number of Ways of Cutting a Pizza
**Difficulty:** HARD
[External](https://leetcode.com/problems/number-of-ways-of-cutting-a-pizza)
Canonical: https://scaleengineer.com/dsa/problems/number-of-ways-of-cutting-a-pizza
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming), [Memoization](https://scaleengineer.com/dsa/patterns/memoization), [Prefix Sum](https://scaleengineer.com/dsa/patterns/prefix-sum)
**Data structures:** Array, Matrix
---
## Problem
Given a rectangular pizza represented as a `rows x cols` matrix containing the following characters: `'A'` (an apple) and `'.'` (empty cell) and given the integer `k`. You have to cut the pizza into `k` pieces using `k-1` cuts. 

For each cut you choose the direction: vertical or horizontal, then you choose a cut position at the cell boundary and cut the pizza into two pieces. If you cut the pizza vertically, give the left part of the pizza to a person. If you cut the pizza horizontally, give the upper part of the pizza to a person. Give the last piece of pizza to the last person.

_Return the number of ways of cutting the pizza such that each piece contains **at least** one apple._ Since the answer can be a huge number, return this modulo 10^9 + 7.

**Example 1:**

**![](https://assets.glich.co/dsa/number-of-ways-of-cutting-a-pizza/image0.png)**

**Input:** pizza = ["A..","AAA","..."], k = 3
**Output:** 3 
**Explanation:** The figure above shows the three ways to cut the pizza. Note that pieces must contain at least one apple.

**Example 2:**

**Input:** pizza = ["A..","AA.","..."], k = 3
**Output:** 1

**Example 3:**

**Input:** pizza = ["A..","A..","..."], k = 1
**Output:** 1

**Constraints:**

* `1 <= rows, cols <= 50`
* `rows == pizza.length`
* `cols == pizza[i].length`
* `1 <= k <= 10`
* `pizza` consists of characters `'A'` and `'.'` only.

# Approaches
## Brute-force Recursion
This approach uses a straightforward recursive function to explore all possible sequences of `k-1` cuts. The function's state is defined by the current top-left corner of the pizza being considered and the number of cuts still to be made. It systematically tries every possible horizontal and vertical cut. For each cut, it checks if the piece being given away contains at least one apple. If it does, it makes a recursive call for the remaining piece of pizza with one fewer cut. The total number of ways is the sum of the results from all valid recursive calls.
**Time:** O((rows + cols)^k). This is a rough estimate. For each of the `k-1` cuts, there are up to `rows + cols - 2` choices. Since subproblems are recomputed, the complexity is exponential, making it too slow for the given constraints. · **Space:** O(rows * cols + k). `O(rows * cols)` is for the suffix sum grid `apples`, and `O(k)` is for the depth of the recursion call stack.
**Pros:** Conceptually simple and directly translates the problem statement into code.; Serves as a good foundation for more optimized dynamic programming solutions.
**Cons:** Extremely inefficient due to a massive number of redundant computations for the same subproblems (same `row`, `col`, and `cuts_left`).; Will result in a 'Time Limit Exceeded' (TLE) error for all but the smallest test cases.
### Explanation
The core of this method is a recursive helper function, let's call it `solve(row, col, cuts_left)`. This function calculates the number of valid ways to cut the sub-pizza whose top-left corner is at `(row, col)` and extends to the original pizza's bottom-right corner, given that we still need to make `cuts_left` cuts.

To avoid repeatedly scanning the grid to check for apples, we first pre-process the pizza into a 2D suffix sum array, `apples`. `apples[i][j]` will store the total number of apples in the rectangle from `(i, j)` to `(rows-1, cols-1)`. This allows us to determine if any rectangular piece has apples in constant time.

The recursion proceeds by exploring all valid cuts. A horizontal cut at row `h` is valid if the top piece (rows `row` to `h-1`) has apples. A vertical cut at column `v` is valid if the left piece (columns `col` to `v-1`) has apples. For each valid cut, we recurse on the remaining piece. The base case for the recursion is when `cuts_left` becomes 0. At this point, if the final remaining piece has at least one apple, we've found one valid way.

However, this naive recursion re-solves the same subproblems multiple times. For example, `solve(r, c, cuts)` might be called through different sequences of initial cuts, leading to an exponential number of calls.
### Algorithm
1. Pre-compute a 2D suffix sum grid `apples` where `apples[i][j]` stores the number of apples in the rectangular sub-pizza from `(i, j)` to `(rows-1, cols-1)`. This allows for O(1) queries to find the number of apples in any rectangular piece.
2. Define a recursive function `solve(row, col, cuts_left)` that returns the number of ways to cut the pizza starting at `(row, col)` with `cuts_left` cuts remaining.
3. **Base Case:** If `cuts_left` is 0, it means we have made `k-1` cuts. The current sub-pizza is the last piece. If it contains at least one apple (i.e., `apples[row][col] > 0`), we have found one valid sequence of cuts, so return 1. Otherwise, return 0.
4. **Recursive Step:**
   - Initialize `count = 0`.
   - **Horizontal Cuts:** Iterate through all possible horizontal cut positions `h` from `row + 1` to `rows - 1`. For each `h`, the top piece is the rectangle from `(row, col)` to `(h-1, cols-1)`. Check if this piece has at least one apple using the pre-computed `apples` grid. If it does, this is a valid first cut. Recursively call `solve(h, col, cuts_left - 1)` for the remaining bottom piece and add the result to `count`.
   - **Vertical Cuts:** Similarly, iterate through all vertical cut positions `v` from `col + 1` to `cols - 1`. If the left piece has an apple, recursively call `solve(row, v, cuts_left - 1)` for the remaining right piece and add the result to `count`.
5. Return the total `count` modulo 10^9 + 7.
6. The initial call to start the process is `solve(0, 0, k - 1)`.

## Recursion with Memoization (Top-Down DP)
This approach significantly optimizes the brute-force recursion by using memoization, a technique also known as top-down dynamic programming. The key idea is to store the results of subproblems so that we don't have to re-compute them. We use a 3D array, `memo[cuts][row][col]`, to store the result for each state. Before the function computes the number of ways for a given state, it first checks if the result is already in the `memo` table. If it is, it returns the stored value. Otherwise, it computes the result, stores it in the table for future use, and then returns it. This avoids the exponential complexity of the naive recursive solution.
**Time:** O(k * rows * cols * (rows + cols)). There are `k * rows * cols` states. For each state, we iterate through `O(rows)` possible horizontal cuts and `O(cols)` possible vertical cuts. · **Space:** O(k * rows * cols). This is dominated by the size of the memoization table. The recursion stack adds `O(k)`.
**Pros:** Efficient enough to pass within the given constraints.; Relatively intuitive to implement as it follows the logical flow of recursion.; Correctly handles overlapping subproblems.
**Cons:** Uses `O(k * rows * cols)` space for the memoization table, which can be significant.; May have a slight performance overhead compared to the iterative version due to recursion function calls.
### Explanation
This method enhances the previous recursive solution by adding a cache (memoization table) to store the results of subproblems that have already been solved. The state of a subproblem is uniquely identified by `(cuts_left, row, col)`. We use a 3D array, `memo`, for this purpose.

The recursive function `solve(row, col, cuts_left)` first checks `memo[cuts_left][row][col]`. If a value exists, it's returned directly, preventing re-computation. If not, the function proceeds as before: it calculates the number of ways by trying all valid horizontal and vertical cuts and summing the results from the corresponding recursive calls. The final computed value is then stored in `memo[cuts_left][row][col]` before being returned. This ensures that each of the `k * rows * cols` possible states is computed at most once, drastically improving the time complexity.

```java
class Solution {
    private int MOD = 1_000_000_007;
    private int rows;
    private int cols;
    private Integer[][][] memo;
    private int[][] apples;

    public int ways(String[] pizza, int k) {
        rows = pizza.length;
        cols = pizza[0].length();
        memo = new Integer[k][rows][cols];
        apples = new int[rows + 1][cols + 1];

        // Precompute suffix sums of apples
        for (int r = rows - 1; r >= 0; r--) {
            for (int c = cols - 1; c >= 0; c--) {
                apples[r][c] = (pizza[r].charAt(c) == 'A' ? 1 : 0) 
                             + apples[r + 1][c] 
                             + apples[r][c + 1] 
                             - apples[r + 1][c + 1];
            }
        }

        return solve(0, 0, k - 1);
    }

    private int solve(int r, int c, int cuts) {
        // If the current piece has no apples, no valid cuts can be made.
        if (apples[r][c] == 0) {
            return 0;
        }
        // Base case: k-1 cuts made, this is the last piece.
        // If it has at least one apple (checked above), it's a valid way.
        if (cuts == 0) {
            return 1;
        }
        // If result is already computed, return it.
        if (memo[cuts][r][c] != null) {
            return memo[cuts][r][c];
        }

        long count = 0;

        // Horizontal cuts
        for (int nr = r + 1; nr < rows; nr++) {
            // Check if the upper piece has at least one apple
            if (apples[r][c] - apples[nr][c] > 0) {
                count = (count + solve(nr, c, cuts - 1)) % MOD;
            }
        }

        // Vertical cuts
        for (int nc = c + 1; nc < cols; nc++) {
            // Check if the left piece has at least one apple
            if (apples[r][c] - apples[r][nc] > 0) {
                count = (count + solve(r, nc, cuts - 1)) % MOD;
            }
        }

        return memo[cuts][r][c] = (int) count;
    }
}
```
### Algorithm
1. Pre-compute the `apples` suffix sum grid, same as the brute-force approach.
2. Create a 3D memoization table, `memo[k][rows][cols]`, initialized with a sentinel value (e.g., `null` or -1) to indicate that a state has not been computed.
3. Define the recursive function `solve(row, col, cuts_left)`.
4. At the beginning of the function, check if `memo[cuts_left][row][col]` has been computed. If yes, return the stored value immediately.
5. If the current piece from `(row, col)` has no apples (`apples[row][col] == 0`), no valid cuts are possible. Return 0.
6. **Base Case:** If `cuts_left == 0`, return 1 (since the check for apples in the current piece passed in step 5).
7. **Recursive Step:** Perform the same logic as the brute-force approach to iterate through horizontal and vertical cuts, making recursive calls for valid cuts.
8. Before returning the computed `count`, store it in the memoization table: `memo[cuts_left][row][col] = count`.
9. Return the `count`.
10. The initial call is `solve(0, 0, k - 1)`.

## Iterative Dynamic Programming (Bottom-Up DP)
This approach, also known as bottom-up dynamic programming, is an iterative version of the memoized recursion. It eliminates recursion entirely, often leading to better performance by avoiding function call overhead and potential stack overflow issues. We build the solution from the simplest case (0 cuts) up to the desired `k-1` cuts. We use a DP table, `dp[r][c]`, to store the number of ways to cut the pizza starting at `(r, c)` for a given number of cuts. By iterating from 0 to `k-1` cuts, we can compute the values for the current number of cuts based on the values computed for the previous number of cuts. This approach can also be space-optimized, as calculating the ways for `c` cuts only requires the results for `c-1` cuts.
**Time:** O(k * rows * cols * (rows + cols)). The complexity is determined by the nested loops: `k` for cuts, `rows*cols` for the cells, and `rows+cols` for iterating through possible cut locations. · **Space:** O(rows * cols). We need space for the `apples` grid and two `dp` tables (current and previous), each of size `rows * cols`.
**Pros:** Generally the most performant solution in practice due to the absence of recursion overhead.; Avoids potential stack overflow errors for very deep recursion (though not an issue with `k <= 10`).; Space complexity is optimized to `O(rows * cols)` instead of `O(k * rows * cols)`.
**Cons:** The logic can be slightly less intuitive to formulate compared to the top-down recursive approach.
### Explanation
The bottom-up DP approach tabulates the results iteratively. We start with the base case: the number of ways to have 1 piece (i.e., 0 cuts). This is 1 for any sub-pizza that contains at least one apple, and 0 otherwise. We store this in a 2D array `dp[rows][cols]`.

Then, we iterate from `cuts = 1` to `k-1`. In each iteration, we compute the number of ways to get `cuts + 1` pieces. We use a new table, `newDp`, to store these results. The value `newDp[r][c]` is calculated by summing up the valid ways from the previous `dp` table. A horizontal cut at `h` contributes `dp[h][c]` ways if the top piece is valid. A vertical cut at `v` contributes `dp[r][v]` ways if the left piece is valid. After filling the `newDp` table for all `(r, c)`, we replace the old `dp` table with `newDp` and proceed to the next number of cuts.

This process continues until we have computed the results for `k-1` cuts. The final answer is the value at `dp[0][0]`.

```java
class Solution {
    public int ways(String[] pizza, int k) {
        int rows = pizza.length;
        int cols = pizza[0].length();
        int MOD = 1_000_000_007;

        int[][] apples = new int[rows + 1][cols + 1];
        for (int r = rows - 1; r >= 0; r--) {
            for (int c = cols - 1; c >= 0; c--) {
                apples[r][c] = (pizza[r].charAt(c) == 'A' ? 1 : 0) 
                             + apples[r + 1][c] 
                             + apples[r][c + 1] 
                             - apples[r + 1][c + 1];
            }
        }

        int[][] dp = new int[rows][cols];
        // Base case: for 1 piece (0 cuts), there's 1 way if the piece has an apple.
        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                if (apples[r][c] > 0) {
                    dp[r][c] = 1;
                }
            }
        }

        // Iterate for number of cuts from 1 to k-1
        for (int cuts = 1; cuts < k; cuts++) {
            int[][] newDp = new int[rows][cols];
            for (int r = 0; r < rows; r++) {
                for (int c = 0; c < cols; c++) {
                    long count = 0;
                    // Horizontal cuts
                    for (int nr = r + 1; nr < rows; nr++) {
                        // Check if upper piece has an apple
                        if (apples[r][c] > apples[nr][c]) {
                            count = (count + dp[nr][c]) % MOD;
                        }
                    }
                    // Vertical cuts
                    for (int nc = c + 1; nc < cols; nc++) {
                        // Check if left piece has an apple
                        if (apples[r][c] > apples[r][nc]) {
                            count = (count + dp[r][nc]) % MOD;
                        }
                    }
                    newDp[r][c] = (int) count;
                }
            }
            dp = newDp;
        }

        return dp[0][0];
    }
}
```
### Algorithm
1. Pre-compute the `apples` suffix sum grid as in the other approaches.
2. Create a 2D DP table, `dp[rows][cols]`. This will store the number of ways for the current number of cuts being processed.
3. **Base Case (k=1 piece, 0 cuts):** Initialize `dp[r][c] = 1` if the sub-pizza from `(r, c)` has at least one apple (`apples[r][c] > 0`), and `0` otherwise. This `dp` table now holds the answers for making 0 cuts.
4. **Iteration:** Loop for the number of cuts `c` from 1 to `k-1`.
   - Inside this loop, create a `newDp[rows][cols]` table to store the results for the current number of cuts `c`.
   - Iterate through each cell `(r, c)` from `(0, 0)` to `(rows-1, cols-1)`.
   - To calculate `newDp[r][c]`, sum up the ways from the previous state (`dp` table):
     - **Horizontal Cuts:** Iterate `h` from `r + 1` to `rows - 1`. If the top piece (from `r` to `h-1`) has an apple, add `dp[h][c]` to the total for `newDp[r][c]`.
     - **Vertical Cuts:** Iterate `v` from `c + 1` to `cols - 1`. If the left piece (from `c` to `v-1`) has an apple, add `dp[r][v]` to the total.
   - After computing `newDp` for all `(r, c)`, update `dp = newDp` for the next iteration.
5. After the loops complete, the answer is `dp[0][0]`, which represents the number of ways to cut the whole pizza `k-1` times.

# Solutions
### Java

```java
class Solution {
private
  int m;
private
  int n;
private
  int[][] s;
private
  Integer[][][] f;
private
  final int mod = (int)1 e9 + 7;
public
  int ways(String[] pizza, int k) {
    m = pizza.length;
    n = pizza[0].length();
    s = new int[m + 1][n + 1];
    f = new Integer[m][n][k];
    for (int i = 1; i <= m; ++i) {
      for (int j = 1; j <= n; ++j) {
        int x = pizza[i - 1].charAt(j - 1) == 'A' ? 1 : 0;
        s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + x;
      }
    }
    return dfs(0, 0, k - 1);
  }
private
  int dfs(int i, int j, int k) {
    if (k == 0) {
      return s[m][n] - s[i][n] - s[m][j] + s[i][j] > 0 ? 1 : 0;
    }
    if (f[i][j][k] != null) {
      return f[i][j][k];
    }
    int ans = 0;
    for (int x = i + 1; x < m; ++x) {
      if (s[x][n] - s[i][n] - s[x][j] + s[i][j] > 0) {
        ans = (ans + dfs(x, j, k - 1)) % mod;
      }
    }
    for (int y = j + 1; y < n; ++y) {
      if (s[m][y] - s[i][y] - s[m][j] + s[i][j] > 0) {
        ans = (ans + dfs(i, y, k - 1)) % mod;
      }
    }
    return f[i][j][k] = ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int ways(vector<string> &pizza, int k) {
    const int mod = 1e9 + 7;
    int m = pizza.size(), n = pizza[0].size();
    vector<vector<vector<int>>> f(m,
                                  vector<vector<int>>(n, vector<int>(k, -1)));
    vector<vector<int>> s(m + 1, vector<int>(n + 1));
    for (int i = 1; i <= m; ++i) {
      for (int j = 1; j <= n; ++j) {
        int x = pizza[i - 1][j - 1] == 'A' ? 1 : 0;
        s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + x;
      }
    }
    function<int(int, int, int)> dfs = [&](int i, int j, int k) -> int {
      if (k == 0) {
        return s[m][n] - s[i][n] - s[m][j] + s[i][j] > 0 ? 1 : 0;
      }
      if (f[i][j][k] != -1) {
        return f[i][j][k];
      }
      int ans = 0;
      for (int x = i + 1; x < m; ++x) {
        if (s[x][n] - s[i][n] - s[x][j] + s[i][j] > 0) {
          ans = (ans + dfs(x, j, k - 1)) % mod;
        }
      }
      for (int y = j + 1; y < n; ++y) {
        if (s[m][y] - s[i][y] - s[m][j] + s[i][j] > 0) {
          ans = (ans + dfs(i, y, k - 1)) % mod;
        }
      }
      return f[i][j][k] = ans;
    };
    return dfs(0, 0, k - 1);
  }
};

```

### Python

```python
class Solution:
    def ways(self, pizza: List[str], k: int) -> int: @ cache def dfs(i: int, j: int, k: int) -> int: if k == 0: return int(s[m][n] - s[i][n] - s[m][j] + s[i][j] > 0) ans = 0 for x in range(i + 1, m): if s[x][n] - s[i][n] - s[x][j] + s[i][j] > 0: ans += dfs(x, j, k - 1) for y in range(j + 1, n): if s[m][y] - s[i][y] - s[m][j] + s[i][j] > 0: ans += dfs(i, y, k - 1) return ans % mod mod = 10 ** 9 + 7 m, n = len(pizza), len(pizza[0]) s = [[0] * (n + 1) for _ in range(m + 1)] for i, row in enumerate(pizza, 1): for j, c in enumerate(row, 1): s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + int(c == 'A') return dfs(0, 0, k - 1)

```