题目描述
有一个 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
的蛋糕块的 最小 总开销。
样例
输入: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 。
输入: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 <= 20
horizontalCut.length == m - 1
verticalCut.length == n - 1
1 <= horizontalCut[i], verticalCut[i] <= 10^3
算法
(动态规划) $O(m^2n^2(m + n))$
- 设状态 $f(x_1, y_1, x_2, y_2)$ 表示将左上角 $(x_1, y_1)$ 与右下角 $(x_2, y_2)$ 形成的矩形分解为
1 x 1
所需要的最小代价。 - 初始时,$f(i, j, i, j) = 0$,其余为正无穷待定。
- 转移时,对于 $f(x_1, y_1, x_2, y_2)$,可以枚举 $x_1 \le i < x_2$,进行水平切割,也可以枚举 $y_1 \le j < y_2$,进行垂直切割。分别进行响应的状态转移
- 最终答案为 $f(0, 0, m - 1, n - 1)$。
时间复杂度
- 状态数为 $O(m^2n^2)$,转移时间为 $O(m + n)$,故总时间复杂度为 $O(m^2n^2(m + n))$。
空间复杂度
- 需要 $O(m^2n^2)$ 的额外空间存储状态。
C++ 代码
const int N = 20;
const int INF = 1000000000;
class Solution {
private:
int f[N][N][N][N];
public:
int minimumCost(
int m, int n,
vector<int>& horizontalCut, vector<int>& verticalCut
) {
for (int x1 = 0; x1 < m; x1++)
for (int y1 = 0; y1 < n; y1++)
for (int x2 = x1; x2 < m; x2++)
for (int y2 = y1; y2 < n; y2++)
f[x1][y1][x2][y2] = INF;
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++)
f[i][j][i][j] = 0;
for (int x1 = m - 1; x1 >= 0; x1--)
for (int y1 = n - 1; y1 >= 0; y1--)
for (int x2 = x1; x2 < m; x2++)
for (int y2 = y1; y2 < n; y2++) {
for (int i = x1; i < x2; i++)
f[x1][y1][x2][y2] = min(
f[x1][y1][x2][y2],
f[x1][y1][i][y2] + f[i + 1][y1][x2][y2]
+ horizontalCut[i]
);
for (int j = y1; j < y2; j++)
f[x1][y1][x2][y2] = min(
f[x1][y1][x2][y2],
f[x1][y1][x2][j] + f[x1][j + 1][x2][y2]
+ verticalCut[j]
);
}
return f[0][0][m - 1][n - 1];
}
};