Number of Ways of Cutting a Pizza

hard prefix sum dynamic programming matrix

Problem

A rows × cols pizza grid holds apples ('A') and empty cells ('.'). Make exactly k − 1 straight cuts to split it into k pieces. Each cut is vertical (give away the left part) or horizontal (give away the top part); the final leftover is the last piece. Count the cutting sequences where every piece contains at least one apple, modulo 10⁹ + 7.

Inputpizza = ["A..","AAA","..."], k = 3

Output3

There are exactly three ways to make 2 cuts so all three pieces each keep an apple.

pizza (rows separated by /)

k (pieces)

def ways(pizza, k):
    MOD = 10**9 + 7
    R, C = len(pizza), len(pizza[0])
    # apples[r][c] = apples in subgrid (r..R-1, c..C-1)
    apples = [[0] * (C + 1) for _ in range(R + 1)]
    for r in range(R - 1, -1, -1):
        for c in range(C - 1, -1, -1):
            apples[r][c] = ((pizza[r][c] == 'A')
                + apples[r + 1][c] + apples[r][c + 1]
                - apples[r + 1][c + 1])

    from functools import lru_cache
    @lru_cache(maxsize=None)
    def dp(r, c, cuts):
        if apples[r][c] == 0:        # piece has no apple
            return 0
        if cuts == 0:                # last piece, valid
            return 1
        total = 0
        for nr in range(r + 1, R):   # horizontal cut: give top
            if apples[r][c] - apples[nr][c] > 0:
                total += dp(nr, c, cuts - 1)
        for nc in range(c + 1, C):   # vertical cut: give left
            if apples[r][c] - apples[r][nc] > 0:
                total += dp(r, nc, cuts - 1)
        return total % MOD

    return dp(0, 0, k - 1) % MOD

function ways(pizza, k) {
  const MOD = 1000000007n;
  const R = pizza.length, C = pizza[0].length;
  // apples[r][c] = apples in subgrid (r..R-1, c..C-1)
  const apples = Array.from({ length: R + 1 }, () => new Array(C + 1).fill(0));
  for (let r = R - 1; r >= 0; r--)
    for (let c = C - 1; c >= 0; c--)
      apples[r][c] = (pizza[r][c] === "A" ? 1 : 0)
        + apples[r + 1][c] + apples[r][c + 1] - apples[r + 1][c + 1];

  const memo = new Map();
  function dp(r, c, cuts) {
    if (apples[r][c] === 0) return 0n;   // no apple
    if (cuts === 0) return 1n;           // last piece, valid
    const key = r * 2500 + c * 50 + cuts;
    if (memo.has(key)) return memo.get(key);
    let total = 0n;
    for (let nr = r + 1; nr < R; nr++)   // horizontal cut: give top
      if (apples[r][c] - apples[nr][c] > 0) total += dp(nr, c, cuts - 1);
    for (let nc = c + 1; nc < C; nc++)   // vertical cut: give left
      if (apples[r][c] - apples[r][nc] > 0) total += dp(r, nc, cuts - 1);
    total %= MOD;
    memo.set(key, total);
    return total;
  }
  return Number(dp(0, 0, k - 1) % MOD);
}

int MOD = 1_000_000_007;
int R, C;
int[][] apples;
Long[][][] memo;

int ways(String[] pizza, int k) {
    R = pizza.length; C = pizza[0].length();
    apples = new int[R + 1][C + 1];            // suffix apple counts
    for (int r = R - 1; r >= 0; r--)
        for (int c = C - 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];
    memo = new Long[R][C][k];
    return (int) dp(0, 0, k - 1);
}

long dp(int r, int c, int cuts) {
    if (apples[r][c] == 0) return 0;           // no apple
    if (cuts == 0) return 1;                    // last piece, valid
    if (memo[r][c][cuts] != null) return memo[r][c][cuts];
    long total = 0;
    for (int nr = r + 1; nr < R; nr++)          // horizontal cut: give top
        if (apples[r][c] - apples[nr][c] > 0) total += dp(nr, c, cuts - 1);
    for (int nc = c + 1; nc < C; nc++)          // vertical cut: give left
        if (apples[r][c] - apples[r][nc] > 0) total += dp(r, nc, cuts - 1);
    return memo[r][c][cuts] = total % MOD;
}

int ways(vector<string>& pizza, int k) {
    const int MOD = 1e9 + 7;
    int R = pizza.size(), C = pizza[0].size();
    // apples[r][c] = apples in subgrid (r..R-1, c..C-1)
    vector<vector<int>> apples(R + 1, vector<int>(C + 1, 0));
    for (int r = R - 1; r >= 0; r--)
        for (int c = C - 1; c >= 0; c--)
            apples[r][c] = (pizza[r][c] == 'A')
                + apples[r + 1][c] + apples[r][c + 1] - apples[r + 1][c + 1];

    vector<vector<vector<long long>>> memo(R, vector<vector<long long>>(C, vector<long long>(k, -1)));
    function<long long(int,int,int)> dp = [&](int r, int c, int cuts) -> long long {
        if (apples[r][c] == 0) return 0;       // no apple
        if (cuts == 0) return 1;                // last piece, valid
        if (memo[r][c][cuts] != -1) return memo[r][c][cuts];
        long long total = 0;
        for (int nr = r + 1; nr < R; nr++)      // horizontal cut: give top
            if (apples[r][c] - apples[nr][c] > 0) total += dp(nr, c, cuts - 1);
        for (int nc = c + 1; nc < C; nc++)      // vertical cut: give left
            if (apples[r][c] - apples[r][nc] > 0) total += dp(r, nc, cuts - 1);
        return memo[r][c][cuts] = total % MOD;
    };
    return dp(0, 0, k - 1);
}

Explanation

Every cut throws away either the left strip (vertical cut) or the top strip (horizontal cut), so the piece that remains always keeps the bottom-right corner (R−1, C−1). That means a remaining piece is fully described by just its upper-left corner (r, c). This is the key observation that makes the state space small.

To answer "does a region contain an apple?" in O(1), we precompute a suffix prefix-sum grid apples, where apples[r][c] is the number of apples in the subgrid from (r, c) down to the bottom-right corner. We fill it bottom-up with the 2D inclusion–exclusion identity apples[r][c] = cell + apples[r+1][c] + apples[r][c+1] − apples[r+1][c+1].

Now define dp(r, c, cuts) = the number of ways to finish cutting the piece anchored at (r, c) using cuts more cuts. If that piece has no apple at all (apples[r][c] == 0) it can never be a valid final piece, so it returns 0. If cuts == 0, the whole remaining piece is the last person's slice and it is valid (it has an apple), so it returns 1.

Otherwise we try every cut line. For a horizontal cut at row nr, the top strip (r..nr−1) must contain an apple — that is apples[r][c] − apples[nr][c] > 0 — and the remaining piece anchors at (nr, c) with one fewer cut. Vertical cuts work symmetrically with columns. We sum all valid recursive results modulo 10⁹ + 7.

Memoizing on (r, c, cuts) means each of the R · C · k states is computed once, and each does O(R + C) work scanning cut positions. Example ["A..","AAA","..."], k = 3 yields 3.

Time: O(k · R · C · (R + C)) Space: O(k · R · C)