leetcode：5289. 公平分发饼干【看数据范围 + dfs剪枝】

分析

一开始没看数据范围 想用排序加双指针试试 完全没有想法
然后数据这么小就可以暴力了
就是dfs+回溯 把当前的饼干试试分给每一个小朋友
然后分完之后看看小朋友中的最大值就是最不公平数
然后求一个最小值即可

注意需要剪枝：
如果当前的最大值已经大于记录的最小值就可以剪掉了

ac code

class Solution:
    def distributeCookies(self, cookies: List[int], k: int) -> int:
        n = len(cookies)
        #own = [0] * k
        ans = inf
        
        def dfs(now, own):
            #print(now, own)
            nonlocal ans
            if now == n:
                ans = min(ans, max(own))
                return
            
            if max(own) >= ans:
                return
            
            for i in range(k):
                own[i] += cookies[now]
                dfs(now + 1, own)
                own[i] -= cookies[now]
        
        dfs(0, [0] * k)
        
        return ans
                
            

总结

dfs没有剪枝吃了一波超时
注意dfs之后有没有显然的剪枝方法