LeetCode 1444. 切披萨的方案数

Categories:

Tags:

题目描述
思路分析
1. 解法一：二维前缀和 + 三维 DP（推荐）
相似题目

题目描述

✅ 1444. 切披萨的方案数

思路分析

解法一：二维前缀和 + 三维 DP（推荐）

核心思路：

用二维前缀和 suffix[r][c] 预处理从 (r, c) 到右下角的苹果数量，支持 O(1) 查询任意子矩形的苹果数。

定义 dp[k][r][c] 表示将从 (r, c) 到右下角的矩形切成 k 块（每块至少含一个苹果）的方案数。

切横刀：枚举切割行 r'（r' > r），若上方矩形 (r, c)-(r'-1, cols-1) 含苹果，则 dp[k][r][c] += dp[k-1][r'][c]。

切竖刀：枚举切割列 c'（c' > c），若左方矩形 (r, c)-(rows-1, c'-1) 含苹果，则 dp[k][r][c] += dp[k-1][r][c']。

最终答案为 dp[k][0][0]，答案对 1e9+7 取模。

复杂度分析：

时间复杂度：O(k × rows × cols × (rows + cols))，其中 k 为切割块数，rows 和 cols 分别为矩阵行列数

空间复杂度：O(k × rows × cols)，用于存储三维 DP 数组和二维前缀和数组

class Solution {
    private static final int MOD = 1_000_000_007;

    public int ways(String[] pizza, int k) {
        int rows = pizza.length;
        int cols = pizza[0].length();

        // 构建二维后缀和：suffix[r][c] 表示从 (r,c) 到右下角的苹果数
        int[][] suffix = new int[rows + 1][cols + 1];
        for (int r = rows - 1; r >= 0; r--) {
            for (int c = cols - 1; c >= 0; c--) {
                int apple = pizza[r].charAt(c) == 'A' ? 1 : 0;
                suffix[r][c] = apple + suffix[r + 1][c] + suffix[r][c + 1] - suffix[r + 1][c + 1];
            }
        }

        // 查询子矩形 (r1,c1) 到 (r2,c2) 的苹果数
        // apples(r, c) = suffix[r][c] - suffix[rows][c] - suffix[r][cols] + suffix[rows][cols]
        // 简化：suffix[r][c] 已表示 (r,c) 到右下角，所以用差分即可
        // apples in top-half when horizontal cut at r': suffix[r][c] - suffix[r'][c]
        // apples in left-half when vertical cut at c': suffix[r][c] - suffix[r][c']

        // dp[piece][r][c]：从 (r,c) 到右下角切成 piece 块的方案数
        int[][][] dp = new int[k + 1][rows][cols];

        // 初始化：切 1 块，即不切割，只要该区域有苹果就是 1 种方案
        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                dp[1][r][c] = suffix[r][c] > 0 ? 1 : 0;
            }
        }

        // 枚举块数
        for (int piece = 2; piece <= k; piece++) {
            for (int r = 0; r < rows; r++) {
                for (int c = 0; c < cols; c++) {
                    // 切横刀：在 r' 行上方切割，上方矩形为 (r, c) 到 (r'-1, cols-1)
                    for (int r2 = r + 1; r2 < rows; r2++) {
                        // 判断上方矩形是否含苹果
                        if (suffix[r][c] - suffix[r2][c] > 0) {
                            dp[piece][r][c] = (dp[piece][r][c] + dp[piece - 1][r2][c]) % MOD;
                        }
                    }
                    // 切竖刀：在 c' 列左方切割，左方矩形为 (r, c) 到 (rows-1, c'-1)
                    for (int c2 = c + 1; c2 < cols; c2++) {
                        // 判断左方矩形是否含苹果
                        if (suffix[r][c] - suffix[r][c2] > 0) {
                            dp[piece][r][c] = (dp[piece][r][c] + dp[piece - 1][r][c2]) % MOD;
                        }
                    }
                }
            }
        }

        return dp[k][0][0];
    }
}

func ways(pizza []string, k int) int {
    const mod = 1_000_000_007
    rows := len(pizza)
    cols := len(pizza[0])

    // 构建二维后缀和：suffix[r][c] 表示从 (r,c) 到右下角的苹果数
    suffix := make([][]int, rows+1)
    for i := range suffix {
        suffix[i] = make([]int, cols+1)
    }
    for r := rows - 1; r >= 0; r-- {
        for c := cols - 1; c >= 0; c-- {
            apple := 0
            if pizza[r][c] == 'A' {
                apple = 1
            }
            suffix[r][c] = apple + suffix[r+1][c] + suffix[r][c+1] - suffix[r+1][c+1]
        }
    }

    // dp[piece][r][c]：从 (r,c) 到右下角切成 piece 块的方案数
    dp := make([][][]int, k+1)
    for i := range dp {
        dp[i] = make([][]int, rows)
        for j := range dp[i] {
            dp[i][j] = make([]int, cols)
        }
    }

    // 初始化：切 1 块，只要该区域有苹果就是 1 种方案
    for r := 0; r < rows; r++ {
        for c := 0; c < cols; c++ {
            if suffix[r][c] > 0 {
                dp[1][r][c] = 1
            }
        }
    }

    // 枚举块数
    for piece := 2; piece <= k; piece++ {
        for r := 0; r < rows; r++ {
            for c := 0; c < cols; c++ {
                // 切横刀：上方矩形为 (r,c) 到 (r2-1, cols-1)，需含苹果
                for r2 := r + 1; r2 < rows; r2++ {
                    if suffix[r][c]-suffix[r2][c] > 0 {
                        dp[piece][r][c] = (dp[piece][r][c] + dp[piece-1][r2][c]) % mod
                    }
                }
                // 切竖刀：左方矩形为 (r,c) 到 (rows-1, c2-1)，需含苹果
                for c2 := c + 1; c2 < cols; c2++ {
                    if suffix[r][c]-suffix[r][c2] > 0 {
                        dp[piece][r][c] = (dp[piece][r][c] + dp[piece-1][r][c2]) % mod
                    }
                }
            }
        }
    }

    return dp[k][0][0]
}

相似题目

题目	难度	考察点
221. 最大正方形	中等	二维 DP、前缀和
1277. 统计全为 1 的正方形子矩阵	中等	二维 DP
1314. 矩阵区域和	中等	二维前缀和
1504. 统计全 1 子矩形	中等	二维前缀和、单调栈
312. 戳气球	困难	区间 DP
410. 分割数组的最大值	困难	二分 + DP、前缀和
813. 最大平均值和的分组	中等	分组 DP、前缀和

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2025/20942564