在Python中查找切割木棒的最小成本程序

假设我们有一个值n和名为cuts的数组。考虑一根长度为n个单位的木棒。木棍从0到n标记。这里的cuts [i]表示我们可以切割的位置。我们应按顺序执行切割，但我们可以随意更改切割的顺序。这里一个切割的成本是要切的木棍的大小，总成本是所有切割的成本之和。我们必须找到切割的最小总成本。

因此，如果输入是n = 7，cuts = [5,1,4,3]，则输出将是16，因为如果我们按[3,5,1,4]的顺序排序，那么首先在长度为7的位置上割3，所以成本为7，然后我们有两个长度为3和4的部分，然后在5处割，所以成本为4，至今为止总共是7 + 4 = 11，然后从长度为2的木棍先割4，所以总成本7 + 4 + 2 = 13，然后最终割3，所以成本为3，最终的成本为7 + 4 + 2 + 3 = 16。

为了解决这个问题，我们将遵循以下步骤−

cuts：元素为切割位置的列表，以排序顺序排列，并在开头插入0并在结尾插入n
m：cuts的大小
cost：制作大小为m x m的方阵并填充为0
循环k在范围2到m-1中执行
- 循环i在范围0到m-1中执行
  - j = i + k
  - 如果j≥m，则
  - 继续下一次迭代
  - cost [i，j] =（cuts [j] – cuts [i]）+（最小的（cost [i，s] + cost [s，j]）为s在范围内（i + 1，j -1）的所有s）
- 返回cost [0，m-1]

示例

让我们看看以下实现以获得更好的理解

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))