JavaInterview JavaInterview
首页
指南
分类
标签
归档
  • CSDN (opens new window)
  • 文档集合 (opens new window)
  • 系统架构 (opens new window)
  • 微信号 (opens new window)
  • 公众号 (opens new window)

『Java面试+Java学习』
首页
指南
分类
标签
归档
  • CSDN (opens new window)
  • 文档集合 (opens new window)
  • 系统架构 (opens new window)
  • 微信号 (opens new window)
  • 公众号 (opens new window)
  • 指南
  • 简历

  • Java

  • 面试

  • 算法

  • algorithm
  • leetcode
JavaInterview.cn
2025-05-06
目录

切披萨的方案数Java

文章发布较早,内容可能过时,阅读注意甄别。

# 题目

给你一个 rows x cols 大小的矩形披萨和一个整数 k ,矩形包含两种字符: 'A' (表示苹果)和 '.' (表示空白格子)。你需要切披萨 k-1 次,得到 k 块披萨并送给别人。

切披萨的每一刀,先要选择是向垂直还是水平方向切,再在矩形的边界上选一个切的位置,将披萨一分为二。如果垂直地切披萨,那么需要把左边的部分送给一个人,如果水平地切,那么需要把上面的部分送给一个人。在切完最后一刀后,需要把剩下来的一块送给最后一个人。

请你返回确保每一块披萨包含 至少 一个苹果的切披萨方案数。由于答案可能是个很大的数字,请你返回它对 10^9 + 7 取余的结果。

示例 1: ways_to_cut_apple_1.png

输入: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

# 总结

  • 分析出几种情况,然后分别对各个情况实现
微信 支付宝
#Java
最近更新
01
1637. 两点之间不包含任何点的最宽垂直区域 Java
06-26
02
1636. 按照频率将数组升序排序 Java
06-26
03
1638. 统计只差一个字符的子串数目 Java
06-26
更多文章>
Theme by Vdoing | Copyright © 2019-2025 JavaInterview.cn
  • 跟随系统
  • 浅色模式
  • 深色模式
  • 阅读模式