找到在 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
以上是 找到在 Python 中砍一根棍子的最低成本的程序 的全部内容， 来源链接： utcz.com/z/363236.html
