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.
1class Solution {
2 private static final int MOD = 1000000007;
3 public int ways(String[] pizza, int k) {
4 int rows = pizza.length, cols = pizza[0].length();
5 int[][] prefix = new int[rows + 1][cols + 1];
6 for (int r = rows - 1; r >= 0; r--) {
7 for (int c = cols - 1; c >= 0; c--) {
8 prefix[r][c] = (pizza[r].charAt(c) == 'A' ? 1 : 0) + prefix[r + 1][c] + prefix[r][c + 1] - prefix[r + 1][c + 1];
9 }
10 }
11
12 Integer[][][] dp = new Integer[rows][cols][k + 1];
13 return getWays(0, 0, k - 1, rows, cols, dp, prefix);
14 }
15
16 private int getWays(int r, int c, int cuts, int rows, int cols, Integer[][][] dp, int[][] prefix) {
17 if (cuts == 0) return prefix[r][c] > 0 ? 1 : 0;
18 if (dp[r][c][cuts] != null) return dp[r][c][cuts];
19 int ways = 0;
20 for (int nr = r + 1; nr < rows; nr++) {
21 if (prefix[r][c] - prefix[nr][c] > 0) {
22 ways = (ways + getWays(nr, c, cuts - 1, rows, cols, dp, prefix)) % MOD;
23 }
24 }
25 for (int nc = c + 1; nc < cols; nc++) {
26 if (prefix[r][c] - prefix[r][nc] > 0) {
27 ways = (ways + getWays(r, nc, cuts - 1, rows, cols, dp, prefix)) % MOD;
28 }
29 }
30 return dp[r][c][cuts] = ways;
31 }
32}The Java implementation uses a recursive approach with memoization, utilizing a 3D array to keep track of calculated values while leveraging prefix sums to check the presence of apples in subregions.
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.
1const MOD = 1e9 + 7;
2
The JavaScript version follows the same logic using a bottom-up dynamic programming approach, iteratively filling the DP table referencing each subregion cut possibility.