Posted on 2023-05-28 21:52
Uriel 阅读(31)
评论(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)