1
2023-06-30：给你一个 rows * cols 大小的矩形披萨和一个整数 k， 矩形包含两种字符： ‘A‘ （表示苹果）和 ‘.‘ （表示空白格子）， 你需要切披萨 k-1 次，得到 k 块披
作者：福大大架构师每日一题
- 2023-06-30 北京
本文字数：9665 字
阅读完需：约 32 分钟
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 完整代码如下：
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);}
复制代码
划线
评论
复制
发布于: 刚刚阅读数: 4
版权声明: 本文为 InfoQ 作者【福大大架构师每日一题】的原创文章。
原文链接:【http://xie.infoq.cn/article/6a58a937e138d8d5eecfc5c5c】。
本文遵守【CC-BY 4.0】协议，转载请保留原文出处及本版权声明。
福大大架构师每日一题
关注
公众号：福大大架构师每日一题 2021-02-15 加入
公众号：福大大架构师每日一题
评论