LeetCode 1444. 切披萨的方案数
目录
题目描述
题意分析
给定一个 $m \times n$ 的字符矩阵表示披萨，字符
A表示这一格有苹果，.表示没有。要把披萨分给 $k$ 个人，因此需要切 $k-1$ 刀，最终得到 $k$ 块，且每一块都必须至少包含一个苹果。求切法总数，结果对 $10^9+7$ 取模。切割方式受到严格限制，这是全题最重要的约束信号：每一刀要么沿水平方向、要么沿垂直方向，且必须贯穿当前这块披萨；切完之后，把上面那部分或左边那部分分给一个人拿走，自己继续持有剩下的部分接着切。
这条规则带来一个决定性的结构性质：无论切了多少刀，我留在手里的那块披萨永远是原矩阵的一个右下角子矩形。因为每一刀只会砍掉顶部若干行或左侧若干列，右边界和下边界从始至终不动。于是「当前状态」只需要两个数就能完整描述——剩余部分的左上角坐标。
取模要求提示答案规模会很大，说明这是计数问题而非枚举问题，必须用递推而不是真的把方案列出来。数据规模上 $m$、$n$ 与 $k$ 都不大，允许一个状态数为三者乘积、转移代价为 $O(m+n)$ 的算法。
边界方面要注意：最后剩在自己手里的那一块也是 $k$ 块中的一块，同样必须含苹果，不能只检查被切走的部分；另外整个披萨可能一个苹果都没有，此时答案为 $0$。
解法：后缀苹果数 + 记忆化搜索
核心思路
每一刀只会切走当前披萨的上部或左部，因此手中继续切的部分始终是一个右下角子矩形。状态不需要记录四条边，只要记录它的左上角坐标
(row, col)。为了 $O(1)$ 判断切出的区域是否有苹果，预处理二维后缀和：
\[apples[row][col] = apples[row+1][col] + apples[row][col+1] - apples[row+1][col+1] + value(row,col)\]apples[row][col]表示从(row, col)到右下角的苹果数。递推式为定义
dfs(row, col, pieces)：把左上角为(row, col)的右下角子矩形切成pieces块，且每块都有苹果的方案数。
- 横切到
nextRow：切走的上部含苹果，当且仅当apples[row][col] - apples[nextRow][col] > 0；剩余状态为dfs(nextRow, col, pieces - 1)。- 竖切到
nextCol：切走的左部含苹果，当且仅当apples[row][col] - apples[row][nextCol] > 0；剩余状态为dfs(row, nextCol, pieces - 1)。边界是：剩余苹果数少于
pieces时必然无解；pieces == 1时，只要当前区域有苹果就有一种方案。用记忆化缓存三元状态，避免不同切割路径重复计算同一子问题。正确性来自按「第一刀」分类：任意合法方案都有唯一的第一刀方向和位置，转移枚举了全部可能；被切走部分由后缀和保证含苹果，剩余部分由递归继续保证，所以不会计入非法方案，也不会重复或遗漏。
解题步骤
- 从右下向左上计算
apples，额外补一行一列零值哨兵以统一边界。- 建立三维缓存
memo[row][col][pieces]，用-1表示尚未计算，因为合法方案数本身可能为0。- 进入搜索后，若
apples[row][col] < pieces，返回0；若pieces == 1，返回1。- 枚举所有横切位置，只有切走的上部含苹果时才递归到下方子矩形。
- 枚举所有竖切位置，只有切走的左部含苹果时才递归到右方子矩形。
- 将所有子状态方案数相加并对 $10^9+7$ 取模，写入缓存后返回。
对
["A..", "AAA", "..."]、k = 3：第一刀横切掉首行后，第二刀有两种合法竖切位置；第一刀竖切掉首列后，第二刀还有一种合法竖切位置，共3种。
代码实现
import java.util.Arrays;
class Solution {
private static final int MOD = 1_000_000_007;
private int rows;
private int cols;
private int[][] apples;
private int[][][] memo;
public int ways(String[] pizza, int k) {
rows = pizza.length;
cols = pizza[0].length();
apples = new int[rows + 1][cols + 1];
for (int row = rows - 1; row >= 0; row--) {
for (int col = cols - 1; col >= 0; col--) {
apples[row][col] = apples[row + 1][col] + apples[row][col + 1]
- apples[row + 1][col + 1]
+ (pizza[row].charAt(col) == 'A' ? 1 : 0);
}
}
memo = new int[rows][cols][k + 1];
for (int row = 0; row < rows; row++) {
for (int col = 0; col < cols; col++) {
Arrays.fill(memo[row][col], -1);
}
}
return dfs(0, 0, k);
}
private int dfs(int row, int col, int pieces) {
if (apples[row][col] < pieces) {
return 0;
}
if (pieces == 1) {
return 1;
}
if (memo[row][col][pieces] != -1) {
return memo[row][col][pieces];
}
int ans = 0;
for (int nextRow = row + 1; nextRow < rows; nextRow++) {
if (apples[row][col] - apples[nextRow][col] > 0) {
ans = (ans + dfs(nextRow, col, pieces - 1)) % MOD;
}
}
for (int nextCol = col + 1; nextCol < cols; nextCol++) {
if (apples[row][col] - apples[row][nextCol] > 0) {
ans = (ans + dfs(row, nextCol, pieces - 1)) % MOD;
}
}
memo[row][col][pieces] = ans;
return ans;
}
}
func ways(pizza []string, k int) int {
const mod = 1_000_000_007
rows, cols := len(pizza), len(pizza[0])
apples := make([][]int, rows+1)
for row := range apples {
apples[row] = make([]int, cols+1)
}
for row := rows - 1; row >= 0; row-- {
for col := cols - 1; col >= 0; col-- {
apples[row][col] = apples[row+1][col] + apples[row][col+1] -
apples[row+1][col+1]
if pizza[row][col] == 'A' {
apples[row][col]++
}
}
}
memo := make([][][]int, rows)
for row := range memo {
memo[row] = make([][]int, cols)
for col := range memo[row] {
memo[row][col] = make([]int, k+1)
for pieces := range memo[row][col] {
memo[row][col][pieces] = -1
}
}
}
var dfs func(int, int, int) int
dfs = func(row, col, pieces int) int {
if apples[row][col] < pieces {
return 0
}
if pieces == 1 {
return 1
}
if memo[row][col][pieces] != -1 {
return memo[row][col][pieces]
}
ans := 0
for nextRow := row + 1; nextRow < rows; nextRow++ {
if apples[row][col]-apples[nextRow][col] > 0 {
ans = (ans + dfs(nextRow, col, pieces-1)) % mod
}
}
for nextCol := col + 1; nextCol < cols; nextCol++ {
if apples[row][col]-apples[row][nextCol] > 0 {
ans = (ans + dfs(row, nextCol, pieces-1)) % mod
}
}
memo[row][col][pieces] = ans
return ans
}
return dfs(0, 0, k)
}
复杂度分析
- 时间复杂度：$O(kmn(m+n))$。共有 $O(kmn)$ 个状态，每个状态最多枚举 $m-1$ 个横切位置和 $n-1$ 个竖切位置；后缀和预处理的 $O(mn)$ 被主项覆盖。
- 空间复杂度：$O(kmn)$。三维缓存占主导；后缀和为 $O(mn)$，递归深度最多为 $k$。
关键点总结
- 「每刀切走上部或左部」保证剩余区域固定右下角，使状态从四条边压缩为左上角两个坐标。
- 后缀和把「切走部分是否含苹果」降为一次减法，是转移能高效枚举的前提。
- 状态必须包含剩余块数；相同矩形在需要切成不同块数时答案不同。
- 按第一刀分类可直接证明转移不重不漏，递归负责验证最后留下的部分。
- 用
apples[row][col] < pieces提前剪掉苹果数不足的状态。
易错点总结
- 只检查切走的部分，未验证最后留下的部分；递归边界必须保证当前区域也含苹果。
- 把横切判据误写成「剩余部分有苹果」；真正要先检查的是被交出去的上部，即两个后缀和之差。
- 允许
nextRow == rows或nextCol == cols，会把空区域留给后续的人。- 用
0表示缓存未计算，导致答案确实为0的状态被反复搜索。- 后缀和漏减重叠区域
apples[row+1][col+1]，会重复计算右下区域的苹果。- 累加方案数时不及时取模，容易在其他语言或更大约束下溢出。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 304. 二维区域和检索 - 矩阵不可变 | 中等 | 只练二维前缀和的构建与容斥查询，是本题的预处理部分 |
| 312. 戳气球 | 困难 | 同为区间划分计数型 dp，但要枚举最后操作的那个位置 |
| 363. 矩形区域不超过 K 的最大数值和 | 困难 | 同用二维前缀和，目标从计数换成带约束的最值 |
| 410. 分割数组的最大值 | 困难 | 一维分段问题，求最小化最大段和而非方案数 |
| 1043. 分隔数组以得到最大和 | 中等 | 一维分段 dp，段长有上限，转移只需枚举上一刀 |
| 1314. 矩阵区域和 | 中等 | 二维前缀和的直接应用，重点在边界裁剪 |