LeetCode 1444. 切披萨的方案数
题目描述
题意分析
披萨是由苹果格
A和空格.组成的矩形，要经过k - 1刀分给k个人，每个人得到的那一块都必须至少含一个苹果。刀只能沿格子边界横切或竖切，并且要把当前剩余矩形切成两个非空矩形。切割规则限制了接下来能处理哪一块：横切后把上部交出去，只继续切下部；竖切后把左部交出去，只继续切右部。已经交出去的部分不能再切，最后剩下的一块交给最后一个人。因此本题不是把两侧都递归划分，而是逐刀剥去上部或左部。
要求统计所有合法切法，答案对
10^9 + 7取模。苹果总数至少为k只是必要条件，苹果的位置还可能使某些切法无效。
解法：后缀苹果数 + 记忆化搜索
核心思路
[!blue]
每刀只移除上部或左部，所以剩余矩形的右下角始终固定在原披萨的右下角。只需记录左上角
(row, col)就能确定当前区域。再加入还要分出的块数pieces，定义dfs(row, col, pieces)为这块剩余披萨分成pieces份的合法方案数。转移前需要快速判断交出去的那一块是否含苹果。定义
apples[row][col]为从(row, col)到原右下角的苹果总数，从右下向左上递推。当前计数等于下方后缀与右方后缀之和，减去两者重叠的右下后缀，再加当前格子是否有苹果。多补一行一列零值，就能统一处理边缘。横切到第
nextRow行之前时，交出去的是行区间[row, nextRow)，其苹果数为apples[row][col] - apples[nextRow][col]。这个差必须大于零；剩余下部从(nextRow, col)开始，还需要分成pieces - 1份，贡献对应的递归结果。竖切同理，使用两个同一行后缀的差检查左部，再递归右部。如果当前区域的苹果总数少于
pieces，每份至少一苹果不可能满足，立即返回零。如果只需一份，则不再切割；经过前面的苹果数判断后，这一整块已经合法，返回一种方案。枚举切口时不允许落在矩形外边界，避免把空区域留给后面的人。按第一刀的方向和位置划分方案，各分支互不重叠；每条合法切割序列又必然有一个这样的第一刀，所以将所有合法分支的后续方案数相加即可。不同切割历史可能到达相同的剩余矩形和块数，后续选择完全相同，用记忆化缓存复用结果。缓存只复用后续方案数量，不会把不同的前续切法合并成一种。
解题步骤
- 从右下到左上计算二维后缀苹果数，额外保留一行、一列零值处理边界。
- 创建
memo[row][col][pieces]，全部初始化为-1，区别未计算和方案数为零。- 进入搜索时，若当前苹果数小于剩余块数，返回零；若只剩一块，返回一。
- 如果该状态已经计算过，直接返回缓存。
- 枚举
row + 1到最后一行作为下部起点，只有交出的上部有苹果时，才累加下部切成pieces - 1份的方案数。- 枚举
col + 1到最后一列作为右部起点，同样验证左部后累加右部方案数。每次累加立即取模。- 将总数写入缓存并返回，入口为
dfs(0, 0, k)。
代码实现
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))，其中m、n是披萨的行数和列数。后缀和预处理为O(mn)；至多有kmn个状态，每个状态枚举至多m - 1个横切口和n - 1个竖切口，每次判定切走部分只需常数时间。- 空间复杂度：
O(kmn)。缓存大小为O(kmn)，后缀苹果数为O(mn)，递归栈深度至多为k。
关键点总结
[!green]
- 固定交出上部或左部，才使剩余矩形能够只用左上角坐标表示。
- 后缀和的差检查的是已经交出的那一块，递归负责验证后续剩余部分。
- 状态必须包含剩余块数，同一矩形要分给不同人数时方案数不同。
- 第一刀分类保证不重不漏；记忆化复用重复的后续问题，而不是省略不同的切割路径。
易错点总结
[!yellow]
- 切开后递归处理两侧：题目规定上部或左部已经交出，后续只能继续处理下部或右部。
- 只检查剩余部分有苹果：当前交出去的那一份也必须合法，需要先判断对应的后缀计数之差大于零。
pieces == 1时无条件返回一：最后留下的区域也可能没有苹果，应先执行苹果数不足的判断。- 只用苹果总数决定是否可切：苹果数量足够不代表分布允许某个切口，仍需逐刀验证位置。
- 允许切口等于行数或列数：会留下空矩形，切口必须位于当前区域内部。
- 用零表示缓存未计算：零本身也是正确答案，用
-1才能缓存无解状态。- 漏减后缀和的重叠部分或累加后不取模：前者导致苹果被重复计算，后者使多个方案数相加时可能溢出。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 304. 二维区域和检索 - 矩阵不可变 | 中等 | 前缀或后缀矩形和用于常数时间检查被切出的区域是否至少有一个苹果。 |
| 2312. 卖木头块 | 困难 | 同样在矩形上做切割DP，原题两边都能继续切，本题每刀拿走一侧，只递归剩余右下区域。 |