Keep creating , Accelerate growth ！ This is my participation 「 Nuggets day new plan · 6 Yuegengwen challenge 」 Of the 26 God , Click to see the event details
You are given an integer array cookies, where cookies[i] denotes the number of cookies in the ith bag. You are also given an integer k that denotes the number of children to distribute all the bags of cookies to. All the cookies in the same bag must go to the same child and cannot be split up.
The unfairness of a distribution is defined as the maximum total cookies obtained by a single child in the distribution.
Return the minimum unfairness of all distributions.
Example 1:
Input: cookies = [8,15,10,20,8], k = 2
Output: 31
Explanation: One optimal distribution is [8,15,8] and [10,20]
- The 1st child receives [8,15,8] which has a total of 8 + 15 + 8 = 31 cookies.
- The 2nd child receives [10,20] which has a total of 10 + 20 = 30 cookies.
The unfairness of the distribution is max(31,30) = 31.
It can be shown that there is no distribution with an unfairness less than 31.
Copy code Example 2:
Input: cookies = [6,1,3,2,2,4,1,2], k = 3
Output: 7
Explanation: One optimal distribution is [6,1], [3,2,2], and [4,1,2]
- The 1st child receives [6,1] which has a total of 6 + 1 = 7 cookies.
- The 2nd child receives [3,2,2] which has a total of 3 + 2 + 2 = 7 cookies.
- The 3rd child receives [4,1,2] which has a total of 4 + 1 + 2 = 7 cookies.
The unfairness of the distribution is max(7,7,7) = 7.
It can be shown that there is no distribution with an unfairness less than 7.
Copy code Note:
2 <= cookies.length <= 8
1 <= cookies[i] <= 10^5
2 <= k <= cookies.length
Copy code According to the meaning , Given an array of integers cookies, among cookies[i] It means the first one i In a bag cookies Number . There is also an integer k , Means to put all cookie The number of children to whom the bag was distributed . All cookies in the same bag must be given to the same child , Can't be separated . The unfairness of distribution is defined as the gain of a single child in the distribution process cookie Maximum sum . Returns the minimum unfairness of all allocation methods .
This question is a typical retrospective question , If we use violence , find k^n There are different ways to divide , This will definitely time out , We can optimize on this basis , Because backtracking is essentially an optimization of violence , Accelerated the movement of violence .
Define a length of k A list of L , Express k Number of cookies per child , We use recursive methods , Put each biscuit cookies[i] Try to give each child L[j] , And constantly update the maximum value in this allocation process val , When will cookies When it's over , We take val to update result , Then perform the following recursive operation , At the end of the calculation, we get result That's the final answer .
The time complexity is O(k^n) , The space complexity is O(k+n) , there k yes L The length of ,n Is the depth of recursion .
class Solution(object):
def __init__(self):
self.result = float('inf')
def distributeCookies(self, cookies, k):
N = len(cookies)
L = [0] * k
def dfs(i, val):
if val >= self.result:
return
if i == N:
self.result = min(self.result, val)
return
for j in range(k):
L[j] += cookies[i]
dfs(i + 1, max(val, L[j]))
L[j] -= cookies[i]
dfs(0, 0)
return self.result
Copy code Runtime: 45 ms, faster than 84.68% of Python online submissions for Fair Distribution of Cookies.
Memory Usage: 13.5 MB, less than 44.35% of Python online submissions for Fair Distribution of Cookies.
Copy code leetcode.com/contest/wee…
Your support is my greatest motivation
