Number of Ways of Cutting a Pizza

Given a rectangular pizza represented as a rows x cols matrix where 'A' is an apple and '.' is empty, you need to cut the pizza into k pieces using k - 1 cuts. For each cut, you choose a direction (horizontal or vertical) and a position. A horizontal cut gives away everything above the line as one piece. A vertical cut gives away everything to the left as one piece. After the cut, you continue with the remaining bottom-right portion. Every piece must contain at least one apple. Return the number of ways to cut the pizza, modulo 10^9 + 7.

This is LeetCode 1444: Number of Ways of Cutting a Pizza, and it combines two core techniques: 2D suffix sums and grid DP with an extra dimension for the number of cuts. If you have worked through Range Sum Query 2D or Unique Paths, you already know the foundations. This problem layers them together.

The problem

You start with the full pizza. Each cut slices off the top rows (horizontal) or left columns (vertical) as a separate piece, and you keep the remaining bottom-right rectangle. You repeat this k - 1 times to produce k pieces total. The constraint is that every piece, including the final remaining rectangle, must contain at least one apple.

For the pizza ["A..","AAA","..."] with k = 3, the answer is 3. There are exactly 3 ways to make 2 cuts so that all 3 pieces each contain at least one apple.

The approach

The key insight is that after every cut, the remaining pizza is always a sub-rectangle anchored at some (r, c) extending to the bottom-right corner (rows-1, cols-1). This means the DP state only needs three values: the top-left corner (r, c) of the current sub-pizza and the number of cuts remaining.

But before you can write the DP, you need a fast way to check whether a sub-rectangle contains any apples. Iterating over all cells for each check would be too slow. A suffix sum solves this. Define suffix[r][c] as the number of apples in the sub-rectangle from (r, c) to (rows-1, cols-1). You can build this table in O(rows * cols) by filling from bottom-right to top-left:

suffix[r][c] = (pizza[r][c] == 'A') + suffix[r+1][c] + suffix[r][c+1] - suffix[r+1][c+1]

With the suffix table, checking if the sub-rectangle from (r1, c1) to (r2, c2) has apples is just suffix[r1][c1] - suffix[r2+1][c1] - suffix[r1][c2+1] + suffix[r2+1][c2+1] > 0. And since the remaining pizza always extends to the bottom-right corner, you only need suffix[r][c] > 0 to check if the sub-pizza starting at (r, c) has any apples at all.

Step-by-step walkthrough

The code

def ways(pizza, k):
    MOD = 10 ** 9 + 7
    rows, cols = len(pizza), len(pizza[0])

    suffix = [[0] * (cols + 1) for _ in range(rows + 1)]
    for r in range(rows - 1, -1, -1):
        for c in range(cols - 1, -1, -1):
            suffix[r][c] = (
                (1 if pizza[r][c] == "A" else 0)
                + suffix[r + 1][c]
                + suffix[r][c + 1]
                - suffix[r + 1][c + 1]
            )

    dp = [[[0] * k for _ in range(cols)] for _ in range(rows)]

    for r in range(rows):
        for c in range(cols):
            if suffix[r][c] > 0:
                dp[r][c][0] = 1

    for t in range(1, k):
        for r in range(rows):
            for c in range(cols):
                val = 0
                for nr in range(r + 1, rows):
                    top_apples = suffix[r][c] - suffix[nr][c]
                    if top_apples > 0 and suffix[nr][c] > 0:
                        val += dp[nr][c][t - 1]
                for nc in range(c + 1, cols):
                    left_apples = suffix[r][c] - suffix[r][nc]
                    if left_apples > 0 and suffix[r][nc] > 0:
                        val += dp[r][nc][t - 1]
                dp[r][c][t] = val % MOD

    return dp[0][0][k - 1]

The function builds the suffix sum table first, then fills the DP table layer by layer. For each sub-pizza starting at (r, c) and each number of cuts t, it tries every possible horizontal cut (iterating over nr) and every vertical cut (iterating over nc). A cut is valid only if both the removed piece and the remaining piece have at least one apple. The suffix sum makes both checks O(1).

Complexity analysis

Time: O(rows * cols * k * (rows + cols)). There are rows * cols * k DP states. For each state, you iterate over at most rows + cols possible cut positions.

Space: O(rows * cols * k) for the 3D DP table plus O(rows * cols) for the suffix sum. The suffix table is dominated by the DP table when k > 1.

The building blocks

2D suffix sums for sub-rectangle queries

The suffix sum is the mirror image of a prefix sum. Instead of accumulating from top-left to bottom-right, you accumulate from bottom-right to top-left. The advantage for this problem is that the remaining pizza after each cut is always anchored at (r, c) and extends to the bottom-right corner. That means a single lookup suffix[r][c] tells you the total apples in the remaining sub-pizza. No subtraction needed, no four-corner formula. If you have solved Range Sum Query 2D, this is the same idea applied in reverse.

Grid DP with an extra cutting dimension

Standard grid DP problems like Unique Paths or Minimum Path Sum have two dimensions: row and column. This problem adds a third dimension for the number of remaining pieces. The transition is different too. Instead of moving to adjacent cells, you jump to a new starting row or column defined by where you place the cut. This pattern of "DP on sub-rectangles with a resource counter" appears in other partition problems as well.

Edge cases

• k = 1: No cuts needed. If the entire pizza has at least one apple, the answer is 1. Otherwise 0.
• All apples in one row or column: You can only make horizontal cuts below that row (or vertical cuts to its right). Many cut positions will produce empty pieces.
• Grid is 1 x n or n x 1: Only one type of cut is possible (vertical for 1 x n, horizontal for n x 1). The problem reduces to a 1D partition.
• Exactly k apples total: Each piece must get exactly one apple. The number of valid ways depends on the specific layout, but most cut positions will be invalid.

From understanding to recall

You now know how suffix sums enable O(1) apple checks and how the three-dimensional DP counts valid cut sequences. But reproducing this under interview pressure requires more than understanding.

In a timed setting, you need to quickly see that the remaining pizza is always a bottom-right sub-rectangle, decide to use suffix sums instead of prefix sums for cleaner lookups, define the DP state as (row, col, pieces_remaining), and write the transition that tries every horizontal and vertical cut position. That fluency comes from practice, not reading.

Spaced repetition helps you internalize the pattern. You revisit the problem at increasing intervals, each time rebuilding the suffix sum and the three-dimensional DP from scratch. After a few reps, "partition a grid into k pieces" triggers the right template automatically.

Related posts

• Range Sum Query 2D Immutable - The prefix sum technique for 2D sub-rectangle queries, the foundation for the suffix sum used here
• Unique Paths - The simplest grid DP problem, teaching the 2D table structure before adding a cutting dimension
• Minimum Path Sum - Grid DP with optimization, a natural stepping stone toward more complex grid DP problems