题目：

  1. 给你一个整数数组 cuts ，其中 cuts[i] 表示你需要将棍子切开的位置。
  3. 你可以按顺序完成切割，也可以根据需要更改切割的顺序。
  5. 每次切割的成本都是当前要切割的棍子的长度，切棍子的总成本是历次切割成本的总和。
  6. 对棍子进行切割将会把一根木棍分成两根较小的木棍（这两根木棍的长度和就是切割前木棍的长度）。
  7. 请参阅第一个示例以获得更直观的解释。
  9. 返回切棍子的 最小总成本 。
  10. 来源：力扣（LeetCode）
  11. 链接：https://leetcode-cn.com/problems/minimum-cost-to-cut-a-stick
  12. 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

答案：

时间：

30min，不知道怎么初始化边界。

  1. class Solution:
  2.     def minCost(self, n: int, cuts: List[int]) -> int:
  3.         cuts.sort()
  4.         cuts=[0]+cuts+[n]
  5.         m=len(cuts)
  6.         dp=[[float("inf")]*(m) for _ in range(m)]
  8.         dp[0][0] = 0
  9.         for i in range(1,m):
  10.             dp[i][i] = 0;
  11.             dp[i-1][i] = 0;
  13.         for l in range(m-2,-1,-1):
  14.             for r in range(l+1,m):
  15.                 for k in range(l+1,r):
  16.                     dp[l][r]=min(dp[l][r],dp[l][k]+dp[k][r]+cuts[r]-cuts[l])
  17.         return dp[0][m-1]

答案2：记忆化dfs，其实还是区间dp

  1. from functools import lru_cache
  2. class Solution:
  3.     def minCost(self, n: int, cuts: List[int]) -> int:    
  4.         cuts.sort()
  5.         cuts=[0]+cuts+[n]
  6.         m=len(cuts)
  7.         @lru_cache(None)
  8.         def dfs(start,end):
  9.             if end-start==1:return 0
  10.             if end-start==2:return cuts[end]-cuts[start]
  11.             temp=float("inf")
  12.             for k in range(start+1,end):
  13.                 temp=min(temp,dfs(start,k)+dfs(k,end)+cuts[end]-cuts[start])
  14.             return temp
  15.         return dfs(0,m-1)

要点：

1. 区间dp，这次是最小的代价

和上一次最大化不一样，这一次要初始化为无穷，
然而区间大小在0和1 的时候要设置为0
然后就是简单的区间dp，注意一开始设置两个边界。

其他：

代码报错：无