豆包 LeetCode 1444.切披萨的方案数 public int ways(String[] pizza, int k)

下面给你Java 版标准题解，直接可以提交 LeetCode 1444.切披萨的方案数，思路清晰、注释完整。

题目大意

给一个由苹果 A 和 . 组成的披萨（矩阵），要求切 k-1 刀，分成 k 块。
规则：

1. 只能横切或竖切，切完后分给下面/右边
2. 每一块至少有一个苹果
求有多少种切法，答案对 1e9+7 取模。

完整 Java 代码

java
class Solution {
private static final int MOD = 1000000007;

public int ways(String[] pizza, int k) {
int m = pizza.length;
int n = pizza[0].length();

// 后缀和：cnt[i][j] 表示 (i,j) 到右下角的苹果总数
int[][] cnt = new int[m + 1][n + 1];
for (int i = m - 1; i >= 0; i--) {
for (int j = n - 1; j >= 0; j--) {
cnt[i][j] = cnt[i + 1][j] + cnt[i][j + 1] - cnt[i + 1][j + 1]
+ (pizza[i].charAt(j) == 'A' ? 1 : 0);
}
}

// dp[t][i][j]：切 t 刀后，剩余披萨左上角在 (i,j) 的方案数
int[][][] dp = new int[k][m][n];

// 初始：切 0 刀（不切），只要有苹果就是 1 种方案
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
dp[0][i][j] = cnt[i][j] > 0 ? 1 : 0;
}
}

// 枚举切 t 刀
for (int t = 1; t < k; t++) {
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
// 横切：在 i 下面切，x 从 i+1 到 m-1
for (int x = i + 1; x < m; x++) {
if (cnt[i][j] - cnt[x][j] > 0) {
dp[t][i][j] = (dp[t][i][j] + dp[t - 1][x][j]) % MOD;
}
}
// 竖切：在 j 右边切，y 从 j+1 到 n-1
for (int y = j + 1; y < n; y++) {
if (cnt[i][j] - cnt[i][y] > 0) {
dp[t][i][j] = (dp[t][i][j] + dp[t - 1][i][y]) % MOD;
}
}
}
}
}

return dp[k - 1][0][0];
}
}


思路简要

1. 后缀和数组 cnt[i][j]
快速判断任意一块区域有没有苹果。
2. 动态规划 dp[t][i][j] - 状态：切了 t 刀，剩下披萨左上角是 (i,j)
- 转移：- 横切：切在 i 下面，切出的部分必须有苹果
- 竖切：切在 j 右边，切出的部分必须有苹果
- 累加合法转移方案数
3. 答案
切 k-1 刀，从整个披萨 (0,0) 开始的方案数： dp[k-1][0][0]

如果你想要C++ / Python / Go / JS版本，或者需要我逐行精讲复杂度、优化版（前缀和+滚动数组），我可以直接写给你。