2025-03-02：切蛋糕的最小总开销Ⅰ。用go语言，有一个大小为 m x n 的矩形蛋糕，我们需要将其切成 1 x 1 的小

福大大架构师每日一题

发布于 2025-03-03 15:33:16

3800

代码可运行

文章被收录于专栏：福大大架构师每日一题福大大架构师每日一题

运行总次数：0

代码可运行

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 。

沿着水平线 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 main

import (
    "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 {
            return0
        }
        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 math

defminimumCost(m, n, horizontalCut, verticalCut):
    cache = [-1] * (m * m * n * n)
    
    defindex(row1, col1, row2, col2):
        return (row1 * n + col1) * m * n + row2 * n + col2

    defdp(row1, col1, row2, col2):
        if row1 == row2 and col1 == col2:
            return0
        ind = index(row1, col1, row2, col2)
        if cache[ind] >= 0:
            return cache[ind]
        cache[ind] = math.inf
        for i inrange(row1, row2):
            cache[ind] = min(cache[ind], dp(row1, col1, i, col2) + dp(i + 1, col1, row2, col2) + horizontalCut[i])
        for i inrange(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 = 3
n = 2
horizontalCut = [1, 3]
verticalCut = [5]
result = minimumCost(m, n, horizontalCut, verticalCut)
print(result)