LeetCode每日一题1547---切棍子的最小成本
一、题目描述
有一根长度为 n 个单位的木棍，棍上从 0 到 n 标记了若干位置。例如，长度为 6 的棍子可以标记如下：
给你一个整数数组 cuts ，其中 cuts[i] 表示你需要将棍子切开的位置。
你可以按顺序完成切割，也可以根据需要更改切割的顺序。
每次切割的成本都是当前要切割的棍子的长度，切棍子的总成本是历次切割成本的总和。对棍子进行切割将会把一根木棍分成两根较小的木棍（这两根木棍的长度和就是切割前木棍的长度）。请参阅第一个示例以获得更直观的解释。
返回切棍子的 最小总成本 。
示例 1：
输入：n = 7, cuts = [1,3,4,5]
输出：16
解释：按 [1, 3, 4, 5] 的顺序切割的情况如下所示：
第一次切割长度为 7 的棍子，成本为 7 。第二次切割长度为 6 的棍子（即第一次切割得到的第二根棍子），第三次切割为长度 4 的棍子，最后切割长度为 3 的棍子。总成本为 7 + 6 + 4 + 3 = 20 。
而将切割顺序重新排列为 [3, 5, 1, 4] 后，总成本 = 16（如示例图中 7 + 4 + 3 + 2 = 16）。
示例 2：
输入：n = 9, cuts = [5,6,1,4,2]
输出：22
解释：如果按给定的顺序切割，则总成本为 25 。总成本 <= 25 的切割顺序很多，例如，[4, 6, 5, 2, 1] 的总成本 = 22，是所有可能方案中成本最小的。
提示：
2 <= n <= 10^6
1 <= cuts.length <= min(n - 1, 100)
1 <= cuts[i] <= n - 1
cuts 数组中的所有整数都 互不相同
二、解题思路
经典的动态规划问题。方便起见，可以先将cuts按从小到大的顺序进行排序。接下来，这里切割时除了cuts中的位置之外，还存在隐藏边界0和n，方便起见也将这两个数加入到cuts当中。
接下来令f[i][j]表示完成cuts[i]到cuts[j]这一段的切割所需的最小代价，那么对于f[i][j]：
1、若i >= j - 1，说明cuts[i]到cuts[j]之间没有分割点，因此f[i][j] = 0
2、若i < j - 1，那么说明此时存在cuts[i + 1]、cuts[i + 2]、…、cuts[j - 1]这些分割点，那么可以枚举这个分割点cut_pos进行分割，此时分割的代价就是cuts[j] - cuts[i]。另外，此时将棍子分割成了cuts[i]到cuts[cut_pos]以及cuts[cut_pos]到cuts[j]这两个子段，因此就有
f[i][j] = min(f[i][cut_pos] + f[cut_pos][j]) + cuts[j] - cuts[i]
min(f[i][cut_pos] + f[cut_pos][j])，其中cut_pos表示i到j的分割点
其中i < cut_pos < j
动态规划完成后，f[0][len(cuts) - 1]即为最终答案。
在具体实现时，由于需要先计算子段的值，也就意味着需要优先计算下标跨度较小的f，于是可以先从小到大枚举下标跨度l，然后枚举左边界i，通过i + l - 1计算出右边界j。
三、代码
class Solution(object):
def minCost(self, n, cuts):
"""
:type n: int
:type cuts: List[int]
:rtype: int
"""
cuts = [0] + sorted(cuts) + [n]
m = len(cuts)
f = [[None] * m for _ in range(m)]
for l in range(1, m + 1):
for i in range(m):
j = i + l - 1
# 超出边界
if j >= m:
continue
# 没有分割点
if l <= 2:
f[i][j] = 0
else: # 遍历 i 到 j之间的所有分割点 找到最小的代价
for cut_pos in range(i + 1, j):
if f[i][j] is None or f[i][j] > f[i][cut_pos] + f[cut_pos][j]:
f[i][j] = f[i][cut_pos] + f[cut_pos][j]
f[i][j] += cuts[j] - cuts[i]
return f[0][m - 1]