Number of Ways of Cutting a Pizza - Video Solutions

Problem Overview: You are given a rectangular pizza grid where each cell is either an apple ('A') or empty ('.'). The goal is to cut the pizza into k pieces using horizontal or vertical cuts so every piece contains at least one apple. Return the total number of valid ways to perform these cuts.

Approach 1: DP with Prefix Sum + Memoization (Time: O(k * m * n * (m + n)), Space: O(k * m * n))

The key difficulty is quickly checking whether a sub-rectangle contains at least one apple. A 2D prefix sum matrix solves this: it lets you query the apple count of any rectangle in constant time. With that in place, use top-down dynamic programming. Define dfs(r, c, cutsLeft) as the number of ways to cut the submatrix starting at (r, c) with cutsLeft cuts remaining.

From each state, try every possible horizontal cut below the current row and every vertical cut to the right. Before recursing, verify that the piece being separated contains at least one apple using the prefix sum lookup. Memoize the result for each state so repeated subproblems are solved once. This transforms an exponential search into a manageable dynamic programming solution. The approach combines dynamic programming, memoization, and fast region queries over a matrix.

Approach 2: Bottom-Up Dynamic Programming (Time: O(k * m * n * (m + n)), Space: O(k * m * n))

The same recurrence can be computed iteratively instead of recursion. Let dp[c][r][c] represent the number of ways to cut the submatrix starting at (r, c) into c + 1 pieces. Start with the base case where no more cuts are needed and check whether the remaining region contains an apple using the prefix sum matrix.

Then iterate through the number of cuts and accumulate ways by attempting horizontal and vertical cuts. For each candidate cut, confirm the top or left piece contains at least one apple before adding the ways from the remaining subproblem. Bottom-up DP avoids recursion overhead and can be easier to reason about during debugging, but it uses the same state transitions and complexity.

Recommended for interviews: The prefix sum + memoized DFS approach is the one most candidates implement first. It clearly expresses the recursive substructure and shows you understand pruning with fast region queries. Bottom-up DP demonstrates deeper mastery of dynamic programming state transitions, but both solutions rely on the same insight: precompute apple counts and reuse results for overlapping subproblems.