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 強化周 ==