用 Python 编写程序，查找切割木棍的最低成本

pythonserver side programmingprogramming更新于 2025/12/1 22:36:17

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

因此，如果输入为 n = 7，切割 = [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 := 一个列表，其中 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) 内
- 返回 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))