2025-03-02：切蛋糕的最小总开销Ⅰ。用go语言，有一个大小为 m x n 的矩形蛋糕，我们需要将其切成 1 x 1 的小块。
给定两个数组，分别为 horizontalCut 和 verticalCut。horizontalCut 包含了 m-1 个元素，表示在水平线 i 切蛋糕的费用；而 verticalCut 包含了 n-1 个元素，表示在垂直线 j 切蛋糕的费用。
在每次操作中，可以选择非 1 x 1 的矩形蛋糕，进行以下任意一种切割：
1.沿着水平线 i 切割蛋糕，费用为 horizontalCut[i]。
2.沿着垂直线 j 切割蛋糕，费用为 verticalCut[j]。
每次切割后的蛋糕都被分成两个独立的部分，切割费用不受影响，始终保持初始值。
我们的目标是返回将整个蛋糕切成 1 x 1 小块的最小总切割费用。
1 <= m, n <= 20。
horizontalCut.length == m - 1。
verticalCut.length == n - 1。
1 <= horizontalCut[i], verticalCut[i] <= 1000。
输入：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 。
在这里插入图片描述
答案2025-03-02：
chatgpt[1]
题目来自leetcode3218。
大体步骤如下：1.创建一个大小为 m x m x n x n 的缓存数组 cache，用于存储已计算的结果，初始化为 -1；
2.定义一个函数 index，根据给定的行列索引计算在缓存数组中的索引；
3.定义一个递归函数 dp，接受四个参数表示切割的起始和结束位置，并返回切割的最小费用；
4.在 dp 函数中，首先检查是否到达了1x1小块，如果是则返回0，否则计算当前切割的索引，并检查是否已计算过，若已计算则直接返回结果；
5.递归计算水平和垂直切割的最小费用，并更新缓存中的值；
6.最后调用 dp 函数，起始位置为蛋糕的四个角，返回切割成1x1小块的最小总费用；
7.在主函数中给定蛋糕的尺寸和切割费用数组，调用 minimumCost 函数得出结果并打印。
总的时间复杂度为 O(m^3 * n^3)。
总的额外空间复杂度为 O(m^2 * n^2)。
Go完整代码如下：package mainimport ( "fmt" "math")func minimumCost(m int, n int, horizontalCut []int, verticalCut []int) int { cache := make([]int, m*m*n*n) for i := range cache { cache[i] = -1 } index := func(row1, col1, row2, col2 int) int { return (row1*n+col1)*m*n + row2*n + col2 } var dp func(row1, col1, row2, col2 int) int dp = func(row1, col1, row2, col2 int) int { if row1 == row2 && col1 == col2 { return 0 } ind := index(row1, col1, row2, col2) if cache[ind] >= 0 { return cache[ind] } cache[ind] = math.MaxInt32 for i := row1; i < row2; i++ { cache[ind] = min(cache[ind], dp(row1, col1, i, col2)+dp(i+1, col1, row2, col2)+horizontalCut[i]) } for i := col1; i < col2; i++ { cache[ind] = min(cache[ind], dp(row1, col1, row2, i)+dp(row1, i+1, row2, col2)+verticalCut[i]) } return cache[ind] } return dp(0, 0, m-1, n-1)}func main() { m := 3 n := 2 horizontalCut := []int{1, 3} verticalCut := []int{5} result := minimumCost(m, n, horizontalCut, verticalCut) fmt.Println(result)}
在这里插入图片描述
Python完整代码如下：
# -*-coding:utf-8-*-import mathdef minimumCost(m, n, horizontalCut, verticalCut): cache = [-1] * (m * m * n * n) def index(row1, col1, row2, col2): return (row1 * n + col1) * m * n + row2 * n + col2 def dp(row1, col1, row2, col2): if row1 == row2 and col1 == col2: return 0 ind = index(row1, col1, row2, col2) if cache[ind] >= 0: return cache[ind] cache[ind] = math.inf for i in range(row1, row2): cache[ind] = min(cache[ind], dp(row1, col1, i, col2) + dp(i + 1, col1, row2, col2) + horizontalCut[i]) for i in range(col1, col2): cache[ind] = min(cache[ind], dp(row1, col1, row2, i) + dp(row1, i + 1, row2, col2) + verticalCut[i]) return cache[ind] return dp(0, 0, m - 1, n - 1)m = 3n = 2horizontalCut = [1, 3]verticalCut = [5]result = minimumCost(m, n, horizontalCut, verticalCut)print(result)
在这里插入图片描述
引用链接[1] chatgpt: https://chatbotsplace.com/?rc=nnNWSCJ7EP
