切披萨的方案数Java
文章发布较早,内容可能过时,阅读注意甄别。
# 题目
给你一个 rows x cols 大小的矩形披萨和一个整数 k ,矩形包含两种字符: 'A' (表示苹果)和 '.' (表示空白格子)。你需要切披萨 k-1 次,得到 k 块披萨并送给别人。
切披萨的每一刀,先要选择是向垂直还是水平方向切,再在矩形的边界上选一个切的位置,将披萨一分为二。如果垂直地切披萨,那么需要把左边的部分送给一个人,如果水平地切,那么需要把上面的部分送给一个人。在切完最后一刀后,需要把剩下来的一块送给最后一个人。
请你返回确保每一块披萨包含 至少 一个苹果的切披萨方案数。由于答案可能是个很大的数字,请你返回它对 10^9 + 7 取余的结果。
示例 1:
输入:pizza = ["A..","AAA","..."], k = 3
输出:3
解释:上图展示了三种切披萨的方案。注意每一块披萨都至少包含一个苹果。
示例 2:
输入:pizza = ["A..","AA.","..."], k = 3
输出:1
示例 3:
输入:pizza = ["A..","A..","..."], k = 1
输出:1
提示:
- 1 <= rows, cols <= 50
- rows == pizza.length
- cols == pizza[i].length
- 1 <= k <= 10
- pizza 只包含字符 'A' 和 '.' 。
# 思路
dp + 记忆化搜索
# 解法
class Solution {
public int ways(String[] pizza, int k) {
int rows = pizza.length, cols = pizza[0].length();
// 预处理 ans[i][j] 表示剩余 i*j 得披萨时候苹果有多少
int[][] ans = new int[rows+1][cols+1];
for (int i = 1; i <= rows; i++) {
for (int j = 1; j <= cols; j++) {
int p = pizza[rows - i].charAt(cols - j) == 'A' ? 1 : 0;
ans[i][j] = p + ans[i-1][j] + ans[i][j-1] - ans[i-1][j-1];
}
}
if (ans[rows][cols] < k) return 0;
// dp[i][j][k] 表示 剩余 i*j 的披萨时候切 k 刀的合理方案数量
long[][][] dp = new long[rows][cols][k];
// 初始化
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
Arrays.fill(dp[i][j], -1);
dp[i][j][0] = 1;
}
}
return (int) dfs(ans, dp, k-1, rows, cols);
}
private long dfs(int[][] ans, long[][][] dp, int k, int r, int c) {
if (ans[r][c] < k+1) dp[r-1][c-1][k] = 0;
if (dp[r-1][c-1][k] >= 0) return dp[r-1][c-1][k];
// 横切
long res = 0;
for (int i = r-1; i > 0; i--) {
if (ans[r][c] == ans[i][c]) continue;
res = (res + dfs(ans, dp, k - 1, i, c)) % MOD;
}
// 竖切
for (int i = c-1; i > 0; i--) {
if (ans[r][c] == ans[r][i]) continue;
res = (res + dfs(ans, dp, k - 1, r, i)) % MOD;
}
dp[r-1][c-1][k] = res;
return res;
}
int MOD = (int) 1e9 + 7;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
# 总结
- 分析出几种情况,然后分别对各个情况实现



- 01
- 1637. 两点之间不包含任何点的最宽垂直区域 Java06-26
- 02
- 1636. 按照频率将数组升序排序 Java06-26
- 03
- 1638. 统计只差一个字符的子串数目 Java06-26