Sponsored
Sponsored
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.
Time Complexity: O(k * rows^2 * cols^2) due to the nested loops.
Space Complexity: O(k * rows * cols) for the DP table.
1MOD = 10**9 + 7
2
3def ways(pizza, k):
4 rows, cols = len(pizza), len(pizza[0])
5 prefix = [[0] * (cols + 1) for _ in range(rows + 1)]
6 for r in range(rows - 1, -1, -1):
7 for c in range(cols - 1, -1, -1):
8 prefix[r][c] = int(pizza[r][c] == 'A') + prefix[r + 1][c] + prefix[r][c + 1] - prefix[r + 1][c + 1]
9
10 def has_apple(r1, c1, r2, c2):
11 return prefix[r1][c1] - prefix[r2][c1] - prefix[r1][c2] + prefix[r2][c2] > 0
12
13 dp = [[[0] * (k + 1) for _ in range(cols)] for _ in range(rows)]
14 for r in range(rows):
15 for c in range(cols):
16 dp[r][c][1] = 1 if has_apple(r, c, rows, cols) else 0
17
18 for pieces in range(2, k + 1):
19 for r in range(rows):
20 for c in range(cols):
21 for nr in range(r + 1, rows):
22 if has_apple(r, c, nr, cols):
23 dp[r][c][pieces] += dp[nr][c][pieces - 1]
24 dp[r][c][pieces] %= MOD
25 for nc in range(c + 1, cols):
26 if has_apple(r, c, rows, nc):
27 dp[r][c][pieces] += dp[r][nc][pieces - 1]
28 dp[r][c][pieces] %= MOD
29
30 return dp[0][0][k]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.
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.
Time Complexity: O(k * rows^2 * cols^2) due to the nested iteration.
Space Complexity: O(k * rows * cols) for storing DP results.
1public class Solution {
2 private const int MOD = 1000000007;
3 public int Ways(string[] pizza, int k) {
4 int rows = pizza.Length;
5 int cols = pizza[0].Length;
int[,] prefix = new int[rows + 1, cols + 1];
for (int r = rows - 1; r >= 0; r--) {
for (int c = cols - 1; c >= 0; c--) {
prefix[r, c] = (pizza[r][c] == 'A' ? 1 : 0) + prefix[r + 1, c] + prefix[r, c + 1] - prefix[r + 1, c + 1];
}
}
int[,,] dp = new int[rows, cols, k + 1];
for (int r = 0; r < rows; r++) {
for (int c = 0; c < cols; c++) {
dp[r, c, 1] = prefix[r, c] > 0 ? 1 : 0;
}
}
for (int pieces = 2; pieces <= k; pieces++) {
for (int r = 0; r < rows; r++) {
for (int c = 0; c < cols; c++) {
for (int nr = r + 1; nr < rows; nr++) {
if (prefix[r, c] - prefix[nr, c] > 0) {
dp[r, c, pieces] = (dp[r, c, pieces] + dp[nr, c, pieces - 1]) % MOD;
}
}
for (int nc = c + 1; nc < cols; nc++) {
if (prefix[r, c] - prefix[r, nc] > 0) {
dp[r, c, pieces] = (dp[r, c, pieces] + dp[r, nc, pieces - 1]) % MOD;
}
}
}
}
}
return dp[0, 0, k];
}
}The C# implementation uses a bottom-up dynamic programming approach, building the solution iteratively and processing each possible subregion by checking with prefix sums.