找到在 Python 中砍一根棍子的最低成本的程序

假设我们有一个值 n 和一个名为 cut 的数组。假设有一根长度为 n 单位的木棍。棍子标记为从 0 到 n。这里cuts[i] 表示我们可以剪切的位置。我们应该按顺序执行切割，但我们可以根据需要更改切割的顺序。这里一次切割的成本是要切割的棍子的大小，总成本是所有切割成本的总和。我们必须找到削减的最低总成本。

所以，如果输入像 n = 7，cuts = [5,1,4,3]，那么输出将是 16，因为如果我们像 [3,5,1,4] 那样排序它们，那么首先在3 从 7 的长度，所以成本是 7，然后我们有长度 3 和 4 的两个部分，然后在 5 处切割，所以成本是 4，到现在总共是 7+4=11，然后从 2 号木棒切割到 4 ，所以总成本 7+4+2 = 13，然后最终削减为 3，因此成本为 3，最终成本 7+4+2+3 = 16。

示例

让我们看看以下实现以更好地理解

def solve(n, cuts):
   cuts = [0] + sorted(cuts) + [n]
   m = len(cuts)
   cost = [[0]*m for _ in range(m)]

   for k in range(2, m):
      for i in range(m):
         j = i + k
         if j >= m:
            continue
         cost[i][j] = (cuts[j]-cuts[i]) + min(cost[i][s] + cost[s][j] for s in range(i+1, j))

   return cost[0][m-1]

n = 7
cuts = [5,1,4,3]
print(solve(n, cuts))

输入

7, [5,1,4,3]

16