Leecode刷题C语言之切蛋糕的最小总开销①

执行结果:通过

执行用时和内存消耗如下：

int idx(int m, int n, int row1, int col1, int row2, int col2) {return (row1 * n + col1) * m * n + row2 * n + col2;
}int dp(int m, int n, int row1, int col1, int row2, int col2, int *horizontalCut, int *verticalCut, int *cache) {if (row1 == row2 && col1 == col2) {return 0;}int ind = idx(m, n, row1, col1, row2, col2);if (cache[ind] >= 0) {return cache[ind];}cache[ind] = INT_MAX;for (int i = row1; i < row2; i++) {cache[ind] = fmin(cache[ind], dp(m, n, row1, col1, i, col2, horizontalCut, verticalCut, cache) + dp(m, n, i + 1, col1, row2, col2, horizontalCut, verticalCut, cache) + horizontalCut[i]);}for (int i = col1; i < col2; i++) {cache[ind] = fmin(cache[ind], dp(m, n, row1, col1, row2, i, horizontalCut, verticalCut, cache) + dp(m, n, row1, i + 1, row2, col2, horizontalCut, verticalCut, cache) + verticalCut[i]);}return cache[ind];
}int minimumCost(int m, int n, int *horizontalCut, int horizontalCutSize, int *verticalCut, int verticalCutSize) {int *cache = (int *)malloc(m * m * n * n * sizeof(int));memset(cache, 0xff, m * m * n * n * sizeof(int));int res = dp(m, n, 0, 0, m - 1, n - 1, horizontalCut, verticalCut, cache);free(cache);return res;
}

解题思路：

这段代码实现了一个动态规划算法，用于计算将一个矩形切割成多个小矩形的最小成本。矩形的切割可以通过水平方向和垂直方向的切割线来完成。水平方向和垂直方向的切割成本分别由两个数组给出：horizontalCut 和 verticalCut。下面是详细的思路分析：

1. `idx` 函数

目的：生成一个唯一索引，用于在缓存数组 cache 中标识从 (row1, col1) 到 (row2, col2) 区域的切割问题的状态。
实现：首先计算 (row1, col1) 在整个矩形中的一维索引，然后乘以整个矩形的面积（m * n），再加上 (row2, col2) 在剩余部分中的一维索引。
公式：(row1 * n + col1) * m * n + row2 * n + col2
- row1 * n + col1：计算 (row1, col1) 在一维数组中的位置。
- 乘以 m * n：将一维索引转换到整个二维空间的唯一索引。
- 加上 row2 * n + col2：计算 (row2, col2) 在剩余部分（从 (row1, col1) 视角看）中的一维索引。

2. `dp` 函数

目的：使用动态规划计算从 (row1, col1) 到 (row2, col2) 区域切割的最小成本。
基本情况：如果 row1 == row2 && col1 == col2，说明没有需要切割的区域，返回 0。
缓存：使用 cache 数组存储已经计算过的状态，避免重复计算。
递归分割：
- 尝试所有可能的水平切割线（从 row1 到 row2-1），计算并更新最小成本。
- 尝试所有可能的垂直切割线（从 col1 到 col2-1），计算并更新最小成本。
- 每次切割的成本是当前切割线的成本加上分割后两部分的最小切割成本之和。
返回：缓存中存储的最小成本。