1547. Minimum Cost to Cut a Stick
给你一个一根木棍的长度 n 还有预计要切除的所有断点
可以自由决定要切断的顺序
切除有个 cost = 断点所在那根木棍的总长
问你 cost 总和最小是多少
Example 1:
https://assets.leetcode.com/uploads/2020/07/23/e1.jpg
Input: n = 7, cuts = [1,3,4,5]
Output: 16
Explanation: Using cuts order = [1, 3, 4, 5] as in the input leads to the
following scenario:
https://assets.leetcode.com/uploads/2020/07/21/e11.jpg
The first cut is done to a rod of length 7 so the cost is 7. The second cut
is done to a rod of length 6 (i.e. the second part of the first cut), the
third is done to a rod of length 4 and the last cut is to a rod of length 3.
The total cost is 7 + 6 + 4 + 3 = 20.
Rearranging the cuts to be [3, 5, 1, 4] for example will lead to a scenario
with total cost = 16 (as shown in the example photo 7 + 4 + 3 + 2 = 16).
解释好长 总之就是第一张图那样切比较好
Example 2:
Input: n = 9, cuts = [5,6,1,4,2]
Output: 22
Explanation: If you try the given cuts ordering the cost will be 25.
There are much ordering with total cost <= 25, for example, the order [4, 6,
5, 2, 1] has total cost = 22 which is the minimum possible.
思路:
1. 我先想如果有两个断点要怎么决定谁先切
假如长这样: a 断点1 b 断点2 c
先切1 -> cost = a+b+c + 切 (b 断点2 c) 的 cost = a+b+c + b+c
先切2 -> cost = a+b+c + 切 (a 断点1 b) 的 cost = a+b+c + a+b
这样看就有点 dp 的感觉了 对一根从 0~n 的棍子来说
dp[0, n] = n + dp[0, i] + dp[i, n] 在所有 0<i<n 中的最小值
2.因为断点都决定好了 所以上面式子中的 i 要改成 iterate cuts 的 index
dp[i, j] = 目前木棍 也就是断点 i 到断点 j 往下切完的最小 cost
= min([dp[i, k] + dp[k, j] for k in range(i+1, j)]) + 木棍长
就是 i, j 之间的断点一个一个去试看哪个最小
试到什么时候? 就是 j == i+1 的时候 代表他们中间没断点了
Python code:
class Solution:
def minCost(self, n: int, cuts: List[int]) -> int:
cuts.sort()
cuts = [0]+cuts+[n]
@cache
def dp(i, j):
if j-1 == i:
return 0
res = cuts[j] - cuts[i] + min([dp(i, k) + dp(k, j) for k in
range(i+1, j)])
return res
return dp(0, len(cuts)-1)
把头尾也当作断点 算 cuts[j] - cuts[i] 会比较方便
偷懒用了 python 的 cache
DP 强化周 ==

大师

大师