leetcode：5289. Distribute cookies fairly [see data range + DFS pruning]

analysis

I didn't look at the data range at first Want to use sorting plus double pointers to try No idea at all
Then the data is so small that it can be violent
Namely dfs+ to flash back Try the current biscuits and give them to each child
Then, after the score, we can see that the maximum value among the children is the most unfair number
Then find a minimum value

Pay attention to pruning ：
If the current maximum value is greater than the record minimum value, it can be cut off

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
                
            

summary

dfs Without pruning, I ate a wave of overtime
Be careful dfs Is there any obvious pruning method after that