Hard

题目描述

给你一个 rows x cols 大小的矩形披萨，矩阵中只包含字符 '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' 和 '.'

解题思路

这是一道典型的动态规划题目，需要结合前缀和优化查询。

核心思路：

  1. 状态定义：dp[r][c][cuts] 表示从位置 (r,c) 到右下角 (rows-1,cols-1) 的矩形区域，使用 cuts 次切割的方案数
  2. 前缀和优化：预处理前缀和数组 preSum，用于 O(1) 时间判断任意矩形区域是否包含苹果
  3. 状态转移：
    • 尝试所有可能的水平切割：在第 nr 行切割，上半部分 [r,nr) 必须包含苹果
    • 尝试所有可能的垂直切割：在第 nc 列切割，左半部分 [c,nc) 必须包含苹果
    • 递归计算剩余部分的方案数

关键优化：

  • 使用记忆化搜索避免重复计算
  • 前缀和数组实现矩形区域苹果数量的快速查询
  • 及时剪枝：如果当前区域没有足够的苹果，直接返回0

时间复杂度分析：

  • 状态总数：O(rows × cols × k)
  • 每个状态的转移：O(rows + cols)
  • 总时间复杂度：O(rows² × cols × k + rows × cols² × k)

代码实现

class Solution {
public:
    int ways(vector<string>& pizza, int k) {
        const int MOD = 1e9 + 7;
        int rows = pizza.size(), cols = pizza[0].size();
        
        // 计算前缀和，preSum[i][j]表示从(i,j)到右下角的苹果数量
        vector<vector<int>> preSum(rows + 1, vector<int>(cols + 1, 0));
        for (int i = rows - 1; i >= 0; i--) {
            for (int j = cols - 1; j >= 0; j--) {
                preSum[i][j] = preSum[i + 1][j] + preSum[i][j + 1] - preSum[i + 1][j + 1] + (pizza[i][j] == 'A' ? 1 : 0);
            }
        }
        
        // 记忆化搜索
        vector<vector<vector<int>>> memo(rows, vector<vector<int>>(cols, vector<int>(k, -1)));
        
        function<int(int, int, int)> dp = [&](int r, int c, int cuts) -> int {
            // 如果当前区域没有苹果，返回0
            if (preSum[r][c] == 0) return 0;
            // 如果不需要再切，返回1
            if (cuts == 0) return 1;
            // 如果已经计算过，直接返回
            if (memo[r][c][cuts] != -1) return memo[r][c][cuts];
            
            int result = 0;
            
            // 水平切割
            for (int nr = r + 1; nr < rows; nr++) {
                // 上半部分必须有苹果
                if (preSum[r][c] - preSum[nr][c] > 0) {
                    result = (result + dp(nr, c, cuts - 1)) % MOD;
                }
            }
            
            // 垂直切割
            for (int nc = c + 1; nc < cols; nc++) {
                // 左半部分必须有苹果
                if (preSum[r][c] - preSum[r][nc] > 0) {
                    result = (result + dp(r, nc, cuts - 1)) % MOD;
                }
            }
            
            return memo[r][c][cuts] = result;
        };
        
        return dp(0, 0, k - 1);
    }
};

class Solution:
    def ways(self, pizza: List[str], k: int) -> int:
        MOD = 10**9 + 7
        rows, cols = len(pizza), len(pizza[0])
        
        # 计算前缀和，preSum[i][j]表示从(i,j)到右下角的苹果数量
        preSum = [[0] * (cols + 1) for _ in range(rows + 1)]
        for i in range(rows - 1, -1, -1):
            for j in range(cols - 1, -1, -1):
                preSum[i][j] = (preSum[i + 1][j] + preSum[i][j + 1] - 
                               preSum[i + 1][j + 1] + (1 if pizza[i][j] == 'A' else 0))
        
        # 记忆化搜索
        memo = {}
        
        def dp(r, c, cuts):
            # 如果当前区域没有苹果，返回0
            if preSum[r][c] == 0:
                return 0
            # 如果不需要再切，返回1
            if cuts == 0:
                return 1
            # 如果已经计算过，直接返回
            if (r, c, cuts) in memo:
                return memo[(r, c, cuts)]
            
            result = 0
            
            # 水平切割
            for nr in range(r + 1, rows):
                # 上半部分必须有苹果
                if preSum[r][c] - preSum[nr][c] > 0:
                    result = (result + dp(nr, c, cuts - 1)) % MOD
            
            # 垂直切割
            for nc in range(c + 1, cols):
                # 左半部分必须有苹果
                if preSum[r][c] - preSum[r][nc] > 0:
                    result = (result + dp(r, nc, cuts - 1)) % MOD
            
            memo[(r, c, cuts)] = result
            return result
        
        return dp(0, 0, k - 1)

public class Solution {
    public int Ways(string[] pizza, int k) {
        const int MOD = 1000000007;
        int rows = pizza.Length, cols = pizza[0].Length;
        
        // 计算前缀和，preSum[i][j]表示从(i,j)到右下角的苹果数量
        int[,] preSum = new int[rows + 1, cols + 1];
        for (int i = rows - 1; i >= 0; i--) {
            for (int j = cols - 1; j >= 0; j--) {
                preSum[i, j] = preSum[i + 1, j] + preSum[i, j + 1] - 
                               preSum[i + 1, j + 1] + (pizza[i][j] == 'A' ? 1 : 0);
            }
        }
        
        // 记忆化搜索
        int[,,] memo = new int[rows, cols, k];
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                for (int l = 0; l < k; l++) {
                    memo[i, j, l] = -1;
                }
            }
        }
        
        return DP(0, 0, k - 1);
        
        int DP(int r, int c, int cuts) {
            // 如果当前区域没有苹果，返回0
            if (preSum[r, c] == 0) return 0;
            // 如果不需要再切，返回1
            if (cuts == 0) return 1;
            // 如果已经计算过，直接返回
            if (memo[r, c, cuts] != -1) return memo[r, c, cuts];
            
            long result = 0;
            
            // 水平切割
            for (int nr = r + 1; nr < rows; nr++) {
                // 上半部分必须有苹果
                if (preSum[r, c] - preSum[nr, c] > 0) {
                    result = (result + DP(nr, c, cuts - 1)) % MOD;
                }
            }
            
            // 垂直切割
            for (int nc = c + 1; nc < cols; nc++) {
                // 左半部分必须有苹果
                if (preSum[r, c] - preSum[r, nc] > 0) {
                    result = (result + DP(r, nc, cuts - 1)) % MOD;
                }
            }
            
            return memo[r, c, cuts] = (int)result;
        }
    }
}

var ways = function(pizza, k) {
    const MOD = 1000000007;
    const rows = pizza.length;
    const cols = pizza[0].length;
    
    // Precompute apple counts for each rectangle from (i,j) to bottom-right
    const apples = Array(rows + 1).fill().map(() => Array(cols + 1).fill(0));
    
    for (let i = rows - 1; i >= 0; i--) {
        for (let j = cols - 1; j >= 0; j--) {
            apples[i][j] = apples[i + 1][j] + apples[i][j + 1] - apples[i + 1][j + 1];
            if (pizza[i][j] === 'A') {
                apples[i][j]++;
            }
        }
    }
    
    // Memoization
    const memo = {};
    
    function dp(r, c, cuts) {
        if (cuts === 0) {
            return apples[r][c] > 0 ? 1 : 0;
        }
        
        const key = `${r},${c},${cuts}`;
        if (memo[key] !== undefined) {
            return memo[key];
        }
        
        let result = 0;
        
        // Try horizontal cuts
        for (let i = r + 1; i < rows; i++) {
            if (apples[r][c] - apples[i][c] > 0 && apples[i][c] > 0) {
                result = (result + dp(i, c, cuts - 1)) % MOD;
            }
        }
        
        // Try vertical cuts
        for (let j = c + 1; j < cols; j++) {
            if (apples[r][c] - apples[r][j] > 0 && apples[r][j] > 0) {
                result = (result + dp(r, j, cuts - 1)) % MOD;
            }
        }
        
        memo[key] = result;
        return result;
    }
    
    return dp(0, 0, k - 1);
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(rows² × cols × k + rows × cols² × k)
空间复杂度O(rows × cols × k)

其中：

  • 前缀和预处理：O(rows × cols)
  • 动态规划状态数：O(rows × cols × k)
  • 每个状态的转移复杂度：O(rows + cols)
  • 记忆化存储：O(rows × cols × k)

相关题目