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完整代码如下:
在这里插入图片描述
领取专属 10元无门槛券
私享最新 技术干货