Given a rectangular pizza represented as a rows x cols matrix containing the following characters: 'A' (an apple) and '.' (empty cell) and given the integer k. You have to cut the pizza into k pieces using k-1 cuts.
For each cut you choose the direction: vertical or horizontal, then you choose a cut position at the cell boundary and cut the pizza into two pieces. If you cut the pizza vertically, give the left part of the pizza to a person. If you cut the pizza horizontally, give the upper part of the pizza to a person. Give the last piece of pizza to the last person.
Return the number of ways of cutting the pizza such that each piece contains at least one apple. Since the answer can be a huge number, return this modulo 10^9 + 7.
Example 1:
Input: pizza = ["A..","AAA","..."], k = 3 Output: 3 Explanation: The figure above shows the three ways to cut the pizza. Note that pieces must contain at least one apple.
Example 2:
Input: pizza = ["A..","AA.","..."], k = 3 Output: 1
Example 3:
Input: pizza = ["A..","A..","..."], k = 1 Output: 1
Constraints:
1 <= rows, cols <= 50rows == pizza.lengthcols == pizza[i].length1 <= k <= 10pizza consists of characters 'A' and '.' only.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.
This approach leverages a dynamic programming table to store the number of ways to cut sub-pizzas and uses prefix sums to efficiently check if a particular sub-pizza contains apples.
We define a 3D DP array where dp[i][j][k] represents the number of ways to cut the sub-pizza starting from cell (i,j) into k pieces. The base case is when k = 1, where dp[i][j][1] = 1 if the sub-pizza contains at least one apple.
For each position, we attempt both horizontal and vertical cuts and ensure each resulting sub-pizza has at least one 'A'. The prefix sum array helps quickly verify the presence of 'A's within a subregion.
The solution initializes a prefix sum array to check for apples in any subregion of the pizza quickly. The DP table is then filled based on possibilities of horizontal and vertical cuts, ensuring that resulting sub-pizzas have at least one apple.
Time Complexity: O(k * rows^2 * cols^2) due to the nested loops.
Space Complexity: O(k * rows * cols) for the DP table.
This approach is similar in concept to the first DP solution, but it employs a bottom-up strategy, iterating from smaller sub-problems to larger ones. It avoids recursive calls, focusing on building the solution iteratively.
The C# implementation uses a bottom-up dynamic programming approach, building the solution iteratively and processing each possible subregion by checking with prefix sums.
C#
JavaScript
Time Complexity: O(k * rows^2 * cols^2) due to the nested iteration.
Space Complexity: O(k * rows * cols) for storing DP results.
We can use a 2D prefix sum to quickly calculate the number of apples in each sub-rectangle. Define s[i][j] to represent the number of apples in the sub-rectangle that includes the first i rows and the first j columns. Then s[i][j] can be derived from the number of apples in the three sub-rectangles s[i-1][j], s[i][j-1], and s[i-1][j-1]. The specific calculation method is as follows:
$
s[i][j] = s[i-1][j] + s[i][j-1] - s[i-1][j-1] + (pizza[i-1][j-1] == 'A')
Here, pizza[i-1][j-1] represents the character at the i-th row and j-th column in the rectangle. If it is an apple, it is 1; otherwise, it is 0.
Next, we design a function dfs(i, j, k), which represents the number of ways to cut the rectangle (i, j, m-1, n-1) with k cuts to get k+1 pieces of pizza. Here, (i, j) and (m-1, n-1) are the coordinates of the top-left and bottom-right corners of the rectangle, respectively. The calculation method of the function dfs(i, j, k) is as follows:
, it means no more cuts can be made. We need to check if there are any apples in the rectangle. If there are apples, return 1; otherwise, return 0., we need to enumerate the position of the last cut. If the last cut is horizontal, we need to enumerate the cutting position x, where i \lt x \lt m. If s[x][n] - s[i][n] - s[x][j] + s[i][j] \gt 0, it means there are apples in the upper piece of pizza, and we add the value of dfs(x, j, k-1) to the answer. If the last cut is vertical, we need to enumerate the cutting position y, where j \lt y \lt n. If s[m][y] - s[i][y] - s[m][j] + s[i][j] \gt 0, it means there are apples in the left piece of pizza, and we add the value of dfs(i, y, k-1) to the answer.The final answer is the value of dfs(0, 0, k-1).
To avoid repeated calculations, we can use memoized search. We use a 3D array f to record the value of dfs(i, j, k). When we need to calculate the value of dfs(i, j, k), if f[i][j][k] is not -1, it means we have already calculated it before, and we can directly return f[i][j][k]. Otherwise, we calculate the value of dfs(i, j, k) according to the above method and save the result in f[i][j][k].
The time complexity is O(m times n times k times (m + n)), and the space complexity is O(m times n times k). Here, m and n$ are the number of rows and columns of the rectangle, respectively.
Similar problems:
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| DP with Prefix Sum | Time Complexity: O(k * rows^2 * cols^2) due to the nested loops. |
| Bottom-Up Dynamic Programming | Time Complexity: O(k * rows^2 * cols^2) due to the nested iteration. |
| 2D Prefix Sum + Memoized Search | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| DP with Prefix Sum + Memoization | O(k * m * n * (m + n)) | O(k * m * n) | Most intuitive solution. Great for interviews and when recursion with caching is acceptable. |
| Bottom-Up Dynamic Programming | O(k * m * n * (m + n)) | O(k * m * n) | Preferred when avoiding recursion or when you want explicit control over DP state transitions. |
Number of Ways of Cutting a Pizza - (Google, TikTok) | Leetcode-1444 | Explanation ➕ Live Coding • codestorywithMIK • 9,908 views views
Watch 9 more video solutions →Practice Number of Ways of Cutting a Pizza with our built-in code editor and test cases.
Practice on FleetCode