切披萨的方案数【LC1444】
给你一个
rows x cols大小的矩形披萨和一个整数k，矩形包含两种字符：'A'（表示苹果）和'.'（表示空白格子）。你需要切披萨k-1次，得到k块披萨并送给别人。切披萨的每一刀，先要选择是向垂直还是水平方向切，再在矩形的边界上选一个切的位置，将披萨一分为二。如果垂直地切披萨，那么需要把左边的部分送给一个人，如果水平地切，那么需要把上面的部分送给一个人。在切完最后一刀后，需要把剩下来的一块送给最后一个人。
请你返回确保每一块披萨包含 至少一个苹果的切披萨方案数。由于答案可能是个很大的数字，请你返回它对 10^9 + 7 取余的结果。
能独立写出2100+的题啦，保持手感！
dfs+记忆化
- 思路
递归边界：
k 为0无需分割时，检验这块披萨的苹果数目，如果大于0，则为有效分割，返回1；否则返回0
实现
class Solution { int n, m; int[][] sum; int[][][] memo; public static final int MOD = (int)(1e9 + 7); public int ways(String[] pizza, int k) { // 二维前缀和 + 记忆化 n = pizza.length; m = pizza[0].length(); sum = new int[n + 1][m + 1];// 以(x,y)为左上角、以(n-1, m-1)为右下角的区域包含的苹果数目 memo = new int[n][m][k]; for (int i = n - 1; i >= 0; i--){ for (int j = m - 1; j >= 0; j--){ sum[i][j] = sum[i + 1][j] + sum[i][j + 1] - sum[i + 1][j + 1]; if ('A' == pizza[i].charAt(j)){ sum[i][j] += 1; } Arrays.fill(memo[i][j], -1); } } return dfs(0, 0, k - 1); } // 在以(x,y)为左上角、以(n-1, m-1)为右下角的区域，切k刀确保每一块披萨包含至少一个苹果的切披萨方案数 public int dfs(int x, int y, int k){ if (k == 0){ return sum[x][y] > 0 ? 1 : 0; } if (memo[x][y][k] != -1) return memo[x][y][k]; int res = 0; // 枚举行 for (int i = x; i < n - 1; i++){ if (sum[x][y] - sum[i + 1][y] > 0){// 这块披萨为x行至i行 res = (res + dfs(i + 1, y, k- 1)) % MOD; } } // 枚举列 for (int i = y; i < m - 1; i++){ if (sum[x][y] - sum[x][i + 1] > 0){// 这块披萨为y列至i列 res = (res + dfs(x, i + 1, k- 1)) % MOD; } } memo[x][y][k] = res; return res; } }
dp
- 实现
从小到大枚举k
class Solution { public static final int MOD = (int)(1e9 + 7); public int ways(String[] pizza, int k) { // 二维前缀和 + 记忆化 int n = pizza.length; int m = pizza[0].length(); int[][] sum = new int[n + 1][m + 1];// 以(x,y)为左上角、以(n-1, m-1)为右下角的区域包含的苹果数目 int[][][] dp = new int[n][m][k]; for (int i = n - 1; i >= 0; i--){ for (int j = m - 1; j >= 0; j--){ sum[i][j] = sum[i + 1][j] + sum[i][j + 1] - sum[i + 1][j + 1]; if ('A' == pizza[i].charAt(j)){ sum[i][j] += 1; } } } for (int c = 0; c < k; c++){ for (int x = 0; x < n; x++){ for (int y = 0; y < m; y++){ if (c == 0){ dp[x][y][0] = sum[x][y] > 0 ? 1 : 0; continue; } for (int i = x; i < n - 1; i++){ if (sum[x][y] - sum[i + 1][y] > 0){ dp[x][y][c] = (dp[x][y][c] + dp[i + 1][y][c - 1]) % MOD; } } for (int i = y; i < m - 1; i++){ if (sum[x][y] - sum[x][i + 1] > 0){ dp[x][y][c] = (dp[x][y][c] + dp[x][i + 1][c - 1]) % MOD; } } } } } return dp[0][0][k - 1]; } }
