调试中...
中等
相关标签
相关企业
提示
有一个 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
解释：
- 沿着垂直线 0 切开蛋糕，开销为 5 。
- 沿着水平线 0 切开
3 x 1的蛋糕块，开销为 1 。 - 沿着水平线 0 切开
3 x 1的蛋糕块，开销为 1 。 - 沿着水平线 1 切开
2 x 1的蛋糕块，开销为 3 。 - 沿着水平线 1 切开
2 x 1的蛋糕块，开销为 3 。
总开销为 5 + 1 + 1 + 3 + 3 = 13 。
示例 2：
输入：m = 2, n = 2, horizontalCut = [7], verticalCut = [4]
输出：15
解释：
- 沿着水平线 0 切开蛋糕，开销为 7 。
- 沿着垂直线 0 切开
1 x 2的蛋糕块，开销为 4 。 - 沿着垂直线 0 切开
1 x 2的蛋糕块，开销为 4 。
总开销为 7 + 4 + 4 = 15 。
提示：
1 <= m, n <= 20horizontalCut.length == m - 1verticalCut.length == n - 11 <= horizontalCut[i], verticalCut[i] <= 103
通过次数
15.2K
提交次数
22.8K
通过率
66.9%
相关企业
提示 1
The intended solution uses Dynamic Programming.
提示 2
Let
dp[sx][sy][tx][ty] denote the minimum cost to cut the rectangle into 1 x 1 pieces.提示 3
Iterate on the row or column on which you will perform the next cut, after the cut, the current rectangle will be decomposed into two sub-rectangles.
相似题目
评论 (0)
贡献者
© 2025 领扣网络（上海）有限公司
0 人在线
行 1，列 1