2023-06-30：给你一个 rows×cols 大小的矩形披萨和一个整数 k，矩形包含两种字符：‘A‘（表示苹果）

2023-06-30：给你一个 rows * cols 大小的矩形披萨和一个整数 k，

矩形包含两种字符： 'A' （表示苹果）和 '.' （表示空白格子），

你需要切披萨 k-1 次，得到 k 块披萨并送给别人，

切披萨的每一刀，先要选择是向垂直还是水平方向切，再在矩形的边界上选一个切的位置，

将披萨一分为二。如果垂直地切披萨，那么需要把左边的部分送给一个人，

如果水平地切，那么需要把上面的部分送给一个人，

在切完最后一刀后，需要把剩下来的一块送给最后一个人。

请你返回确保每一块披萨包含 至少 一个苹果的切披萨方案数。

由于答案可能是个很大的数字，请你返回它对 10^9 + 7 取余的结果。

输入：pizza = ["A..","AAA","..."], k = 3。

输出：3。

答案2023-06-30：

大体过程如下：

算法1：递归法

1.定义常量 mod = 1000000007。

2.定义函数 ways1(pizza []string, k int) int，接收一个披萨矩形和切割次数 k，返回方案数。

3.获取披萨的行数 n 和列数 m。

4.创建一个二维数组 sum，用于记录每个位置左上角区域内的苹果数量的累加和。

5.调用函数 setAppleMatrix，计算 sum 数组。

6.调用函数 process，传入 sum、n、m、初始行、初始列和切割次数 k。

7.在函数 process 中，首先判断当前切割位置的左上角区域内是否包含苹果，若不包含则返回 0。

8.若切割次数 rest 等于 1，表示只需要切割一次，直接返回 1。

9.初始化变量 ways 为 0，表示方案数。

10.在列方向上进行切割，遍历从当前切割位置 col 开始到第 m 列的所有位置。

10.1.若从当前切割位置到当前列的左上角区域内包含苹果，则递归调用 process 函数，切割位置更新为 i+1，切割次数更新为 rest-1，得到的方案数累加到 ways 中，并对 ways 取模。

11.在行方向上进行切割，遍历从当前切割位置 row 开始到第 n 行的所有位置。

11.1.若从当前切割位置到当前行的左上角区域内包含苹果，则递归调用 process 函数，切割位置更新为 i+1，切割次数更新为 rest-1，得到的方案数累加到 ways 中，并对 ways 取模。

12.返回 ways。

算法2：动态规划法

1.定义常量 mod = 1000000007。

2.定义函数 ways2(pizza []string, k int) int，接收一个披萨矩形和切割次数 k，返回方案数。

3.获取披萨的行数 n 和列数 m。

4.创建一个二维数组 sum，用于记录每个位置左上角区域内的苹果数量的累加和。

5.调用函数 setAppleMatrix，计算 sum 数组。

6.创建一个三维动态规划数组 dp，大小为 k+1 * (n+1) * (m+1)，用于记录切割方案数。

7.初始化 dp 数组的第一层，即切割次数为 1 的情况。遍历披萨的所有位置 (r, c)：

7.1.若从当前切割位置到当前位置的左上角区域内包含苹果，则 dp[1][r][c] = 1。

8.从切割次数为 2 开始，逐层计算 dp 数组，直到切割次数为 k。

9.在每一层 level 中，遍历披萨的所有位置 (row, col)，从最后一行和最后一列开始更新 dp 值：

9.1.初始化变量 ways 为 0，表示方案数。

9.2.在列方向上进行切割，遍历从当前切割位置 col 开始到第 m 列的所有位置 c。

9.2.1.若从当前切割位置到当前列的左上角区域内包含苹果，则遍历切割位置 c+1 到 m 的所有位置 s：

9.2.1.1.将 dp[level-1][row][s] 的方案数累加到 ways 中，并对 ways 取模。

9.2.1.2.当遇到包含苹果的位置时，跳出循环。

9.3.在行方向上进行切割，遍历从当前切割位置 row 开始到第 n 行的所有位置 r。

9.3.1.若从当前切割位置到当前行的左上角区域内包含苹果，则遍历切割位置 r+1 到 n 的所有位置 s：

9.3.1.1.将 dp[level-1][s][col] 的方案数累加到 ways 中，并对 ways 取模。

9.3.1.2.当遇到包含苹果的位置时，跳出循环。

9.4.将 ways 赋值给 dp[level][row][col]。

10.返回 dp[k][1][1]。

算法1：

• 时间复杂度：O(n^2 * m^2 * k)

• 空间复杂度：O(n * m)

算法2：

• 时间复杂度：O(n^2 * m^2 * k)

• 空间复杂度：O(k * n * m)

在这两种算法中，n 是披萨的行数，m 是披萨的列数，k 是需要切割披萨的次数。它们具有相同的时间和空间复杂度，因为它们都采用了类似的动态规划方法来计算切割披萨的方式数量。

注意：通过使用前缀和在常数时间内计算给定子矩阵中苹果数量，可以进一步优化时间复杂性，而不是使用apple()函数，但总体复杂性保持不变。

go完整代码如下：

在这里插入图片描述rust完整代码如下：

在这里插入图片描述c++完整代码如下：

在这里插入图片描述c完整代码如下：

在这里插入图片描述