给你一个 rows * cols 大小的矩形披萨和一个整数 k，
矩形包含两种字符： ‘A’ （表示苹果）和 ‘.’ （表示空白格子），
你需要切披萨 k-1 次，得到 k 块披萨并送给别人，
切披萨的每一刀，先要选择是向垂直还是水平方向切，再在矩形的边界上选一个切的位置，
将披萨一分为二。如果垂直地切披萨，那么需要把左边的部分送给一个人，
如果水平地切，那么需要把上面的部分送给一个人，
在切完最后一刀后，需要把剩下来的一块送给最后一个人。
请你返回确保每一块披萨包含 至少 一个苹果的切披萨方案数。
由于答案可能是个很大的数字，请你返回它对 10^9 + 7 取余的结果。
输入：pizza = [“A…”,“AAA”,“…”], k = 3。
输出：3。
大体过程如下：
算法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完整代码如下：
package main
import (
"fmt"
)
const mod = 1000000007
func ways1(pizza []string, k int) int {
n := len(pizza)
m := len(pizza[0])
sum := make([][]int, n+1)
for i := 0; i <= n; i++ {
sum[i] = make([]int, m+1)
}
setAppleMatrix(pizza, sum, n, m)
return process(sum, n, m, 1, 1, k)
}
func process(sum [][]int, n, m, row, col, rest int) int {
if apple(sum, row, col, n, m) == 0 {
return 0
}
if rest == 1 {
return 1
}
ways := 0
for i := col; i < m; i++ {
if apple(sum, row, col, n, i) > 0 {
ways += process(sum, n, m, row, i+1, rest-1)
ways %= mod
}
}
for i := row; i < n; i++ {
if apple(sum, row, col, i, m) > 0 {
ways += process(sum, n, m, i+1, col, rest-1)
ways %= mod
}
}
return ways
}
func ways2(pizza []string, k int) int {
n := len(pizza)
m := len(pizza[0])
sum := make([][]int, n+1)
for i := 0; i <= n; i++ {
sum[i] = make([]int, m+1)
}
setAppleMatrix(pizza, sum, n, m)
dp := make([][][]int, k+1)
for i := 0; i <= k; i++ {
dp[i] = make([][]int, n+1)
for j := 0; j <= n; j++ {
dp[i][j] = make([]int, m+1)
}
}
for r := 1; r <= n; r++ {
for c := 1; c <= m; c++ {
if apple(sum, r, c, n, m) > 0 {
dp[1][r][c] = 1
}
}
}
for level := 2; level <= k; level++ {
for row := n; row >= 1; row-- {
for col := m; col >= 1; col-- {
ways := 0
for c := col; c < m; c++ {
if apple(sum, row, col, n, c) > 0 {
for s := c + 1; s <= m; s++ {
ways += dp[level-1][row][s]
ways %= mod
}
break
}
}
for r := row; r < n; r++ {
if apple(sum, row, col, r, m) > 0 {
for s := r + 1; s <= n; s++ {
ways += dp[level-1][s][col]
ways %= mod
}
break
}
}
dp[level][row][col] = ways
}
}
}
return dp[k][1][1]
}
func setAppleMatrix(pizza []string, sum [][]int, n, m int) {
for i := 0; i < n; i++ {
for j := 0; j < m; j++ {
if pizza[i][j] == 'A' {
sum[i+1][j+1] = 1
}
}
}
for i := 1; i <= n; i++ {
for j := 1; j <= m; j++ {
sum[i][j] += sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1]
}
}
}
func apple(sum [][]int, a, b, c, d int) int {
return sum[c][d] - sum[c][b-1] - sum[a-1][d] + sum[a-1][b-1]
}
func main() {
pizza := []string{"A..", "AAA", "..."}
k := 3
fmt.Println(ways1(pizza, k))
fmt.Println(ways2(pizza, k))
}
rust完整代码如下：
const MOD: i32 = 1_000_000_007;
fn ways1(pizza: Vec<String>, k: i32) -> i32 {
let n = pizza.len();
let m = pizza[0].len();
let mut sum = vec![vec![0; m + 1]; n + 1];
set_apple_matrix(&pizza, &mut sum, n, m);
process(&sum, n, m, 1, 1, k)
}
fn process(sum: &Vec<Vec<i32>>, n: usize, m: usize, row: usize, col: usize, rest: i32) -> i32 {
if apple(sum, row, col, n, m) == 0 {
return 0;
}
if rest == 1 {
return 1;
}
let mut ways = 0;
for i in col..m {
if apple(sum, row, col, n, i) > 0 {
ways += process(sum, n, m, row, i + 1, rest - 1);
ways %= MOD;
}
}
for i in row..n {
if apple(sum, row, col, i, m) > 0 {
ways += process(sum, n, m, i + 1, col, rest - 1);
ways %= MOD;
}
}
ways
}
fn ways2(pizza: Vec<String>, k: i32) -> i32 {
let n = pizza.len();
let m = pizza[0].len();
let mut sum = vec![vec![0; m + 1]; n + 1];
set_apple_matrix(&pizza, &mut sum, n, m);
let mut dp = vec![vec![vec![0; m + 1]; n + 1]; k as usize + 1];
for r in 1..=n {
for c in 1..=m {
if apple(&sum, r, c, n, m) > 0 {
dp[1][r][c] = 1;
}
}
}
for level in 2..=k as usize {
for row in (1..=n).rev() {
for col in (1..=m).rev() {
let mut ways = 0;
for c in col..m {
if apple(&sum, row, col, n, c) > 0 {
for s in c + 1..=m {
ways += dp[level - 1][row][s];
ways %= MOD;
}
break;
}
}
for r in row..n {
if apple(&sum, row, col, r, m) > 0 {
for s in r + 1..=n {
ways += dp[level - 1][s][col];
ways %= MOD;
}
break;
}
}
dp[level][row][col] = ways;
}
}
}
dp[k as usize][1][1]
}
fn set_apple_matrix(pizza: &Vec<String>, sum: &mut Vec<Vec<i32>>, n: usize, m: usize) {
for i in 0..n {
let row = pizza[i].chars().collect::<Vec<char>>();
for j in 0..m {
sum[i + 1][j + 1] = if row[j] == 'A' { 1 } else { 0 };
}
}
for i in 1..=n {
for j in 1..=m {
sum[i][j] += sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1];
}
}
}
fn apple(sum: &Vec<Vec<i32>>, a: usize, b: usize, c: usize, d: usize) -> i32 {
sum[c][d] - sum[c][b - 1] - sum[a - 1][d] + sum[a - 1][b - 1]
}
fn main() {
let pizza = vec![
String::from("A.."),
String::from("AAA"),
String::from("...")
];
let k = 3;
let res1 = ways1(pizza.clone(), k);
let res2 = ways2(pizza, k);
println!("Result 1: {}", res1);
println!("Result 2: {}", res2);
}
c++完整代码如下：
#include <iostream>
#include <vector>
using namespace std;
const int mod = 1000000007;
void setAppleMatrix(vector<string>& pizza, vector<vector<int>>& sum, int n, int m) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
sum[i + 1][j + 1] = (pizza[i][j] == 'A') ? 1 : 0;
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
sum[i][j] += sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1];
}
}
}
int apple(vector<vector<int>>& sum, int a, int b, int c, int d) {
return sum[c][d] - sum[c][b - 1] - sum[a - 1][d] + sum[a - 1][b - 1];
}
void setNear(vector<vector<int>>& sum, vector<vector<int>>& nearr, vector<vector<int>>& nearc, int n, int m) {
for (int r = 1; r <= n; r++) {
int right = m + 1;
int number = 0;
for (int c = m; c >= 1; c--) {
int curApple = apple(sum, r, c, n, m);
if (curApple > number) {
number = curApple;
right = c;
}
nearc[r][c] = right;
}
}
for (int c = 1; c <= m; c++) {
int down = n + 1;
int number = 0;
for (int r = n; r >= 1; r--) {
int curApple = apple(sum, r, c, n, m);
if (curApple > number) {
number = curApple;
down = r;
}
nearr[r][c] = down;
}
}
}
void setRowColSums(vector<vector<int>>& dp, vector<vector<int>>& rs, vector<vector<int>>& cs, int n, int m) {
rs[n][m] = dp[n][m];
cs[n][m] = dp[n][m];
for (int r = n - 1; r >= 1; r--) {
cs[r][m] = dp[r][m];
rs[r][m] = (dp[r][m] + rs[r + 1][m]) % mod;
}
for (int c = m - 1; c >= 1; c--) {
rs[n][c] = dp[n][c];
cs[n][c] = (dp[n][c] + cs[n][c + 1]) % mod;
}
for (int r = n - 1; r >= 1; r--) {
for (int c = m - 1; c >= 1; c--) {
rs[r][c] = (dp[r][c] + rs[r + 1][c]) % mod;
cs[r][c] = (dp[r][c] + cs[r][c + 1]) % mod;
}
}
}
int process(vector<vector<int>>& sum, int n, int m, int row, int col, int rest);
int ways1(vector<string>& pizza, int k) {
int n = pizza.size();
int m = pizza[0].length();
vector<vector<int>> sum(n + 1, vector<int>(m + 1));
setAppleMatrix(pizza, sum, n, m);
return process(sum, n, m, 1, 1, k);
}
int process(vector<vector<int>>& sum, int n, int m, int row, int col, int rest) {
if (apple(sum, row, col, n, m) == 0) {
return 0;
}
if (rest == 1) {
return 1;
}
int ways = 0;
for (int i = col; i < m; i++) {
if (apple(sum, row, col, n, i) > 0) {
ways += process(sum, n, m, row, i + 1, rest - 1);
ways %= mod;
}
}
for (int i = row; i < n; i++) {
if (apple(sum, row, col, i, m) > 0) {
ways += process(sum, n, m, i + 1, col, rest - 1);
ways %= mod;
}
}
return ways;
}
int ways2(vector<string>& pizza, int k) {
int n = pizza.size();
int m = pizza[0].length();
vector<vector<int>> sum(n + 1, vector<int>(m + 1));
setAppleMatrix(pizza, sum, n, m);
vector<vector<vector<int>>> dp(k + 1, vector<vector<int>>(n + 1, vector<int>(m + 1)));
for (int r = 1; r <= n; r++) {
for (int c = 1; c <= m; c++) {
if (apple(sum, r, c, n, m) > 0) {
dp[1][r][c] = 1;
}
}
}
for (int level = 2; level <= k; level++) {
for (int row = n; row >= 1; row--) {
for (int col = m; col >= 1; col--) {
int ways = 0;
for (int c = col; c < m; c++) {
if (apple(sum, row, col, n, c) > 0) {
for (int s = c + 1; s <= m; s++) {
ways += dp[level - 1][row][s];
ways %= mod;
}
break;
}
}
for (int r = row; r < n; r++) {
if (apple(sum, row, col, r, m) > 0) {
for (int s = r + 1; s <= n; s++) {
ways += dp[level - 1][s][col];
ways %= mod;
}
break;
}
}
dp[level][row][col] = ways;
}
}
}
return dp[k][1][1];
}
int main() {
vector<string> pizza = { "A..", "AAA", "..." };
int k = 3;
int result1 = ways1(pizza, k);
int result2 = ways2(pizza, k);
cout << "Result 1: " << result1 << endl;
cout << "Result 2: " << result2 << endl;
return 0;
}
c完整代码如下：
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define mod 1000000007
void setAppleMatrix(char** pizza, int** sum, int n, int m) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
sum[i + 1][j + 1] = (pizza[i][j] == 'A' ? 1 : 0);
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
sum[i][j] += sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1];
}
}
}
int apple(int** sum, int a, int b, int c, int d) {
return sum[c][d] - sum[c][b - 1] - sum[a - 1][d] + sum[a - 1][b - 1];
}
void setNear(int** sum, int** nearr, int** nearc, int n, int m) {
for (int r = 1; r <= n; r++) {
int right = m + 1;
int number = 0;
for (int c = m; c >= 1; c--) {
int curApple = apple(sum, r, c, n, m);
if (curApple > number) {
number = curApple;
right = c;
}
nearc[r][c] = right;
}
}
for (int c = 1; c <= m; c++) {
int down = n + 1;
int number = 0;
for (int r = n; r >= 1; r--) {
int curApple = apple(sum, r, c, n, m);
if (curApple > number) {
number = curApple;
down = r;
}
nearr[r][c] = down;
}
}
}
void setRowColSums(int** dp, int** rs, int** cs, int n, int m) {
rs[n][m] = dp[n][m];
cs[n][m] = dp[n][m];
for (int r = n - 1; r >= 1; r--) {
cs[r][m] = dp[r][m];
rs[r][m] = (dp[r][m] + rs[r + 1][m]) % mod;
}
for (int c = m - 1; c >= 1; c--) {
rs[n][c] = dp[n][c];
cs[n][c] = (dp[n][c] + cs[n][c + 1]) % mod;
}
for (int r = n - 1; r >= 1; r--) {
for (int c = m - 1; c >= 1; c--) {
rs[r][c] = (dp[r][c] + rs[r + 1][c]) % mod;
cs[r][c] = (dp[r][c] + cs[r][c + 1]) % mod;
}
}
}
int ways1(char** pizza, int pizzaSize, int k) {
int n = pizzaSize;
int m = strlen(pizza[0]);
int** sum = (int**)malloc((n + 1) * sizeof(int*));
for (int i = 0; i <= n; i++) {
sum[i] = (int*)calloc(m + 1, sizeof(int));
}
setAppleMatrix(pizza, sum, n, m);
int result = process(sum, n, m, 1, 1, k);
for (int i = 0; i <= n; i++) {
free(sum[i]);
}
free(sum);
return result;
}
int process(int** sum, int n, int m, int row, int col, int rest) {
if (apple(sum, row, col, n, m) == 0) {
return 0;
}
if (rest == 1) {
return 1;
}
int ways = 0;
for (int i = col; i < m; i++) {
if (apple(sum, row, col, n, i) > 0) {
ways += process(sum, n, m, row, i + 1, rest - 1);
ways %= mod;
}
}
for (int i = row; i < n; i++) {
if (apple(sum, row, col, i, m) > 0) {
ways += process(sum, n, m, i + 1, col, rest - 1);
ways %= mod;
}
}
return ways;
}
int ways2(char** pizza, int pizzaSize, int k) {
int n = pizzaSize;
int m = strlen(pizza[0]);
int** sum = (int**)malloc((n + 1) * sizeof(int*));
for (int i = 0; i <= n; i++) {
sum[i] = (int*)calloc(m + 1, sizeof(int));
}
setAppleMatrix(pizza, sum, n, m);
int*** dp = (int***)malloc((k + 1) * sizeof(int**));
for (int i = 0; i <= k; i++) {
dp[i] = (int**)malloc((n + 1) * sizeof(int*));
for (int j = 0; j <= n; j++) {
dp[i][j] = (int*)calloc(m + 1, sizeof(int));
}
}
for (int r = 1; r <= n; r++) {
for (int c = 1; c <= m; c++) {
if (apple(sum, r, c, n, m) > 0) {
dp[1][r][c] = 1;
}
}
}
int result = 0;
for (int level = 2; level <= k; level++) {
for (int row = n; row >= 1; row--) {
for (int col = m; col >= 1; col--) {
int ways = 0;
for (int c = col; c < m; c++) {
if (apple(sum, row, col, n, c) > 0) {
for (int s = c + 1; s <= m; s++) {
ways += dp[level - 1][row][s];
ways %= mod;
}
break;
}
}
for (int r = row; r < n; r++) {
if (apple(sum, row, col, r, m) > 0) {
for (int s = r + 1; s <= n; s++) {
ways += dp[level - 1][s][col];
ways %= mod;
}
break;
}
}
dp[level][row][col] = ways;
}
}
result = dp[level][1][1];
}
for (int i = 0; i <= k; i++) {
for (int j = 0; j <= n; j++) {
free(dp[i][j]);
}
free(dp[i]);
}
free(dp);
for (int i = 0; i <= n; i++) {
free(sum[i]);
}
free(sum);
return result;
}
int main() {
char* pizza[] = { "A..", "AAA", "..." };
int k = 3;
int result1 = ways1(pizza, sizeof(pizza) / sizeof(pizza[0]), k);
int result2 = ways2(pizza, sizeof(pizza) / sizeof(pizza[0]), k);
printf("Result1: %d\n", result1);
printf("Result2: %d\n", result2);
}
