1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
| class Solution {
private int modulo = (int) 1e9 + 7;
public int ways(String[] pizza, int k) {
int m = pizza.length, n = pizza[0].length();
int[][] prefixSum = new int[m + 1][n + 1];
Integer[][][] dp = new Integer[k][m][n];
for (int i = m - 1; i >= 0; i--) {
int currSum = 0;
for (int j = n - 1; j >= 0; j--) {
currSum += pizza[i].charAt(j) == 'A' ? 1 : 0;
prefixSum[i][j] += prefixSum[i + 1][j] + currSum;
}
}
return dfs(m, n, 0, 0, k - 1, prefixSum, dp);
}
private int dfs(int m, int n, int row, int col, int k, int[][] prefixSum, Integer[][][] dp) {
if (prefixSum[row][col] == 0)
return 0;
if (k == 0)
return 1;
if (dp[k][row][col] != null) {
return dp[k][row][col];
}
int ans = 0;
for (int newRow = row + 1; newRow < m; newRow++) {
if (prefixSum[row][col] - prefixSum[newRow][col] > 0) {
ans = (ans + dfs(m, n, newRow, col, k - 1, prefixSum, dp)) % modulo;
}
}
for (int newCol = col + 1; newCol < n; newCol++) {
if (prefixSum[row][col] - prefixSum[row][newCol] > 0) {
ans = (ans + dfs(m, n, row, newCol, k - 1, prefixSum, dp)) % modulo;
}
}
return dp[k][row][col] = ans;
}
}
|
