Number of Ways of Cutting a Pizza

Number of Ways of Cutting a Pizza dresses up a 2-D dynamic-programming problem with a tasty story. The trick that makes it fast is a suffix prefix-sum table that answers "does this sub-rectangle contain an apple?" in O(1), turning an otherwise expensive recursion into something memoizable.

The slow way first

The naive recursion tries every cut position on every piece and, for each candidate cut, scans the kept piece to check whether it has an apple. Scanning a sub-rectangle is O(R · C), and we do it at every cut on every piece — the repeated scanning is what kills it. There are also overlapping sub-problems: the same remaining piece with the same number of cuts left gets recomputed again and again.

The question to ask: can I answer "does this rectangle have an apple?" without scanning it every time?

The idea: suffix apple counts + memoized cuts

Pre-compute apples[r][c] = the number of apples in the rectangle from (r, c) to the bottom-right corner. Because every piece we ever look at is anchored at some (r, c) and extends to the bottom-right, this single suffix table tells us instantly whether any piece is non-empty: just compare counts. Then dp(r, c, k) = the number of ways to cut the piece whose top-left is (r, c) into k slices, memoized on (r, c, k).

The key insight: a piece anchored at (r, c) "has an apple" exactly when apples[r][c] > 0. A horizontal cut at row nr keeps rows r..nr-1, which has apples[r][c] - apples[nr][c] apples — an O(1) check.

Walk through it

Step through the animation. First we light up the whole pizza to show the suffix count apples[0][0] = 4. Then dp(0, 0, 3) tries a horizontal cut after row 0 and a vertical cut after column 0; each kept piece holds an apple, so each is a legal first cut. Drilling into the lower piece, one more cut splits rows 1 and 2 — both have apples — giving one complete valid cutting. The dp sums all such sequences.

Pseudocode

build apples[r][c] = apples in rectangle (r,c)..(R-1,C-1)   # suffix sums, O(R*C)
 
define dp(r, c, k):                # ways to cut piece at (r,c) into k slices
    if apples[r][c] == 0: return 0 # this piece is empty -> impossible
    if k == 1: return 1            # last slice; it has an apple, so 1 way
    total = 0
    for each horizontal cut row nr below r:
        if kept top piece has an apple: total += dp(nr, c, k-1)
    for each vertical cut col nc right of c:
        if kept left piece has an apple: total += dp(r, nc, k-1)
    return total mod (1e9 + 7)
 
answer = dp(0, 0, k)               # memoize dp on (r, c, k)

The Python solution

def ways(pizza, k):
    R, C = len(pizza), len(pizza[0])
    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])
 
    @cache
    def dp(r, c, k):
        if apples[r][c] == 0:
            return 0
        if k == 1:
            return 1
        total = 0
        for nr in range(r + 1, R):           # horizontal cut
            if apples[r][c] - apples[nr][c] > 0:
                total += dp(nr, c, k - 1)
        for nc in range(c + 1, C):           # vertical cut
            if apples[r][c] - apples[r][nc] > 0:
                total += dp(r, nc, k - 1)
        return total % (10**9 + 7)
    return dp(0, 0, k) % (10**9 + 7)

• apples is padded with an extra zero row and column so the inclusion-exclusion never indexes out of bounds.
• The suffix recurrence adds the cell itself plus the counts below and to the right, then subtracts the double-counted bottom-right block.
• dp(r, c, k) returns the number of ways to finish the piece anchored at (r, c) with k slices; @cache memoizes it on the tuple (r, c, k).
• if apples[r][c] == 0 prunes empty pieces; if k == 1 is the base case — one slice that already has an apple is one valid cutting.
• For each horizontal cut at nr, apples[r][c] - apples[nr][c] is the apples in the kept top piece; if positive, the cut is legal and we recurse on the lower piece with k - 1. The vertical loop is symmetric.

Complexity

The whole win comes from the suffix table: without it each apple check would be O(R · C), multiplying the runtime by the grid size. With it, every check is a single subtraction.

When this pattern shows up

Practice