Medium

题目描述

有一个 m x n 的蛋糕，需要切成 1 x 1 的小块。

给你整数 m、n 和两个数组：

  • horizontalCut 长度为 m - 1，其中 horizontalCut[i] 表示沿第 i 条水平线切割的开销。
  • verticalCut 长度为 n - 1，其中 verticalCut[j] 表示沿第 j 条垂直线切割的开销。

在一次操作中，你可以选择任何一块还不是 1 x 1 正方形的蛋糕，并执行以下切割之一：

  • 沿水平线 i 切割，开销为 horizontalCut[i]。
  • 沿垂直线 j 切割，开销为 verticalCut[j]。

切割后，蛋糕被分成两个不同的部分。

切割的开销只取决于线的初始开销，不会改变。

返回将整个蛋糕切成 1 x 1 块的最小总开销。

示例 1：

输入：m = 3, n = 2, horizontalCut = [1,3], verticalCut = [5]

输出：13

示例 2：

输入：m = 2, n = 2, horizontalCut = [7], verticalCut = [4]

输出：15

提示：

  • 1 <= m, n <= 20
  • horizontalCut.length == m - 1
  • verticalCut.length == n - 1
  • 1 <= horizontalCut[i], verticalCut[i] <= 10³

解题思路

这是一个经典的区间动态规划问题。我们需要找到将蛋糕切成 1x1 小块的最小开销。

核心思路：

对于任意矩形区域，我们可以选择在某条水平线或垂直线进行切割，将其分成两个子矩形。问题转化为：如何选择切割顺序使总开销最小。

动态规划状态定义：

  • dp[sx][sy][tx][ty] 表示将左上角为 (sx,sy)、右下角为 (tx,ty) 的矩形切成 1x1 小块的最小开销

状态转移：

  1. 如果矩形已经是 1x1，开销为 0
  2. 否则枚举所有可能的切割线：
    • 水平切割：在第 i 行切割，开销 = horizontalCut[i] + 上半部分开销 + 下半部分开销
    • 垂直切割：在第 j 列切割，开销 = verticalCut[j] + 左半部分开销 + 右半部分开销

优化思路： 也可以用贪心算法求解。优先选择开销大的切割线，因为先切开销大的线可以减少后续重复切割的次数。但动态规划解法更直观且适用范围更广。

代码实现

class Solution {
public:
    int minimumCost(int m, int n, vector<int>& horizontalCut, vector<int>& verticalCut) {
        vector<vector<vector<vector<int>>>> dp(m, vector<vector<vector<int>>>(n, vector<vector<int>>(m, vector<int>(n, -1))));
        
        function<int(int, int, int, int)> dfs = [&](int sx, int sy, int tx, int ty) -> int {
            if (sx == tx && sy == ty) return 0;
            if (dp[sx][sy][tx][ty] != -1) return dp[sx][sy][tx][ty];
            
            int res = INT_MAX;
            
            // 水平切割
            for (int i = sx; i < tx; i++) {
                int cost = horizontalCut[i] + dfs(sx, sy, i, ty) + dfs(i + 1, sy, tx, ty);
                res = min(res, cost);
            }
            
            // 垂直切割
            for (int j = sy; j < ty; j++) {
                int cost = verticalCut[j] + dfs(sx, sy, tx, j) + dfs(sx, j + 1, tx, ty);
                res = min(res, cost);
            }
            
            return dp[sx][sy][tx][ty] = res;
        };
        
        return dfs(0, 0, m - 1, n - 1);
    }
};

class Solution:
    def minimumCost(self, m: int, n: int, horizontalCut: List[int], verticalCut: List[int]) -> int:
        from functools import lru_cache
        
        @lru_cache(None)
        def dfs(sx, sy, tx, ty):
            if sx == tx and sy == ty:
                return 0
            
            res = float('inf')
            
            # 水平切割
            for i in range(sx, tx):
                cost = horizontalCut[i] + dfs(sx, sy, i, ty) + dfs(i + 1, sy, tx, ty)
                res = min(res, cost)
            
            # 垂直切割
            for j in range(sy, ty):
                cost = verticalCut[j] + dfs(sx, sy, tx, j) + dfs(sx, j + 1, tx, ty)
                res = min(res, cost)
            
            return res
        
        return dfs(0, 0, m - 1, n - 1)

public class Solution {
    private int[,,,] dp;
    private int[] horizontalCut;
    private int[] verticalCut;
    
    public int MinimumCost(int m, int n, int[] horizontalCut, int[] verticalCut) {
        this.dp = new int[m, n, m, n];
        this.horizontalCut = horizontalCut;
        this.verticalCut = verticalCut;
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                for (int k = 0; k < m; k++) {
                    for (int l = 0; l < n; l++) {
                        dp[i, j, k, l] = -1;
                    }
                }
            }
        }
        
        return Dfs(0, 0, m - 1, n - 1);
    }
    
    private int Dfs(int sx, int sy, int tx, int ty) {
        if (sx == tx && sy == ty) return 0;
        if (dp[sx, sy, tx, ty] != -1) return dp[sx, sy, tx, ty];
        
        int res = int.MaxValue;
        
        // 水平切割
        for (int i = sx; i < tx; i++) {
            int cost = horizontalCut[i] + Dfs(sx, sy, i, ty) + Dfs(i + 1, sy, tx, ty);
            res = Math.Min(res, cost);
        }
        
        // 垂直切割
        for (int j = sy; j < ty; j++) {
            int cost = verticalCut[j] + Dfs(sx, sy, tx, j) + Dfs(sx, j + 1, tx, ty);
            res = Math.Min(res, cost);
        }
        
        return dp[sx, sy, tx, ty] = res;
    }
}

var minimumCost = function(m, n, horizontalCut, verticalCut) {
    horizontalCut.sort((a, b) => b - a);
    verticalCut.sort((a, b) => b - a);
    
    let totalCost = 0;
    let hPieces = 1;
    let vPieces = 1;
    let h = 0, v = 0;
    
    while (h < horizontalCut.length && v < verticalCut.length) {
        if (horizontalCut[h] >= verticalCut[v]) {
            totalCost += horizontalCut[h] * vPieces;
            hPieces++;
            h++;
        } else {
            totalCost += verticalCut[v] * hPieces;
            vPieces++;
            v++;
        }
    }
    
    while (h < horizontalCut.length) {
        totalCost += horizontalCut[h] * vPieces;
        h++;
    }
    
    while (v < verticalCut.length) {
        totalCost += verticalCut[v] * hPieces;
        v++;
    }
    
    return totalCost;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型动态规划解法
时间复杂度O(m³n + mn³)
空间复杂度O(m²n²)

说明：

  • 时间复杂度：状态数为 O(m²n²)，每个状态需要枚举 O(m+n) 种切割方式
  • 空间复杂度：记忆化存储需要 O(m²n²) 的空间

相关题目