【LeetCode】每日一题 2024_11_11 切棍子的最小成本（区间 DP，记忆化搜索）

server/2024/11/14 23:41:42/

前言

每天和你一起刷 LeetCode 每日一题~

LeetCode 启动！

题目：leetcode.cn/problems/minimum-cost-to-cut-a-stick/description/?envType=daily-question&envId=2024-11-11" rel="nofollow">切棍子的最小成本

双十一光棍节力扣给我们准备了 . . . 一根棍子

代码与解题思路

先读题：

题目给了 n 代表棍子的长度，给了 cuts 数组代表我们需要在这几个地方砍这根棍子，每次砍的时候会累加当前棍子长度的成本，让我们找出成本最小的砍法

有没有数学的解法我不太清楚，但最简单的思路就是，枚举切割这根棍子的所有情况，找出成本的最小值，那该如何枚举呢？

dfs(i, j)，i j 作为当前木棍的左右边界，我们枚举 k 作为切割的位置，切割后木棍的成本就是：dfs(i, k)+dfs(k, j)，而当前木棍的成本是：cuts[j]-cuts[i]，具体代码如下：

func minCost(n int, cuts []int) int {cuts = append(cuts, 0, n) // 增加头和尾slices.Sort(cuts) // 排序方便操作n = len(cuts) // 现在的 n 是 cuts 数组的长度memo := make([][]int, n)for i := range memo {memo[i] = make([]int, n)}var dfs func(int, int) intdfs = func(i, j int) int { // i j 作为 cuts 数组的下标if i+1 == j { // 中间没有可以切割的点了，不用切割了return 0 }p := &memo[i][j] // 记忆化if *p != 0 {return *p}res := math.MaxIntfor k := i+1; k < j; k++ { // 枚举切割的位置// dfs(i, k)+dfs(k, j) 切割后的两段木棍的成本和res = min(res, dfs(i, k)+dfs(k, j))}*p = res + cuts[j]-cuts[i] // 切割后两段木棍的成本+当前的成本return *p}return dfs(0, n-1)
}