Posted on 2023-05-28 21:52
Uriel 閱讀(49)
評論(0) 編輯 收藏 引用 所屬分類:
DP 、
遞歸 & 分治 、
閑來無事重切Leet Code
一根長度n的棍子，需要在上面cuts (list)的位置切割，每次切割的開銷是當前這一小段的長度，問切割完的最小花費，遞歸DP
和Discussion再次學到lru_cache的用法
1 #1547
2 #Runtime: 761 ms (Beats 87.80%)
3 #Memory: 20.5 MB (Beats 5.95%)
4
5 class Solution:
6 def minCost(self, n: int, cuts: List[int]) -> int:
7 cuts.append(0)
8 cuts.append(n)
9 cuts.sort()
10
11 @functools.lru_cache(None)
12 def dp(x, y):
13 if x >= y - 1:
14 return 0
15 return cuts[y] - cuts[x] + min((dp(x, k) + dp(k, y) for k in range(x + 1, y)), default = 0)
16 return dp(0, len(cuts) - 1)