3218.切蛋糕的最小总开销I

链接：3218.切蛋糕的最小总开销I
难度：Medium
标签：贪心、数组、动态规划、排序
简介：请你返回将蛋糕全部切成 1 x 1 的蛋糕块的 最小 总开销。

题解 1 - python

• 编辑时间：2024-12-25
• 执行用时：2189ms
• 内存消耗：79.68MB
• 编程语言：python
• 解法介绍：记忆化搜索

class Solution:
    def minimumCost(self, n: int, m: int, horizontalCut: List[int], verticalCut: List[int]) -> int:
        @cache
        def dfs(i1: int, i2: int, j1: int, j2: int) -> int:
            if i1 == i2 and j1 == j2: return 0
            res = inf
            for i in range(i1, i2):
                res = min(res, dfs(i1, i, j1, j2) + dfs(i + 1, i2, j1, j2) + horizontalCut[i])
            for j in range(j1, j2):
                res = min(res, dfs(i1, i2, j1, j) + dfs(i1, i2, j + 1, j2) + verticalCut[j])
            return res
        return dfs(0, n - 1, 0, m - 1)