Posted on 2023-07-01 15:30
Uriel 阅读(33)
评论(0) 编辑 收藏 引用 所属分类:
搜索 、
闲来无事重切Leet Code
给出n堆不同数量的cookie，问分给k个人，问拿最多的那个人至少拿多少个cookie，DFS
1 #1514
2 #Runtime: 66 ms (Beats 76.87%)
3 #Memory: 16.2 MB （Beats 98.88%)
4
5 class Solution:
6 def distributeCookies(self, cookies: List[int], k: int) -> int:
7 cnt = [0] * k
8 ans = float('inf')
9 def DFS(c):
10 nonlocal ans
11 if c == len(cookies):
12 ans = min(ans, max(cnt))
13 return
14 for i in range(k):
15 cnt[i] += cookies[c]
16 DFS(c + 1)
17 cnt[i] -= cookies[c]
18 if not cnt[i]:
19 break
20
21 DFS(0)
22 return ans