1547.切棍子的最小成本

链接：1547.切棍子的最小成本
难度：Hard
标签：数组、动态规划、排序
简介：返回切棍子的 最小总成本 。

题解 1 - undefined

• 编辑时间：2024-11-11
• 执行用时：942ms
• 内存消耗：19.98MB
• 编程语言：undefined
• 解法介绍：dfs尝试在每一个点进行切割

class Solution:
    def minCost(self, end: int, cuts: List[int]) -> int:
        @cache
        def dfs(start: int, end: int) -> int:
            res = inf
            for cut in cuts:
                if start < cut < end:
                    res = min(res, dfs(start, cut) + dfs(cut, end) + end - start)
            return res if res != inf else 0
        return dfs(0, end)