The Number of Ways of Cutting a Pizza problem gives you a rectangular pizza grid where each cell either has an apple ('A') or is empty ('.'). You need to make exactly k-1 cuts (horizontal or vertical), dividing the pizza into exactly k pieces, where each piece must contain at least one apple. Count valid ways modulo 10^9+7. This hard DP problem uses 2D prefix sums to check apple counts in sub-rectangles.
Google asks this because it requires 2D prefix sums combined with memoized DP. For each subgrid, checking whether a cut leaves enough apples requires O(1) range queries. The array, matrix, memoization, dynamic programming, and prefix sum interview pattern is fully exercised.
DP with 2D prefix sums. dp[k][r][c] = number of ways to cut the sub-pizza from (r,c) to (R,C) into k pieces with at least one apple each. Precompute apples[r1][c1][r2][c2] = apple count in the rectangle using 2D prefix sums. For each possible horizontal/vertical cut, check if the top/left portion has ≥1 apple, then recurse on the remaining grid. Memoize with (k, r, c) as the state.
Pizza (3×3) with apples at specific positions. k=3 cuts needed. Use 2D prefix sums to check apple count in any sub-rectangle in O(1). For each starting position (r,c), try all horizontal cuts (row r to row r'-1 must have ≥1 apple, then recurse on r' to R). Similarly for vertical cuts. Sum all valid combinations.
2D prefix sums are essential for grid DP problems requiring range sum queries. Build the prefix sum array in O(n²), then compute any rectangle sum as ps[r2+1][c2+1] - ps[r1][c2+1] - ps[r2+1][c1] + ps[r1][c1]. Combine this with memoized DP where states include the top-left corner of the remaining pizza. Practice 2D prefix sums independently, then integrate into grid DP problems.
