得到新鲜甜甜圈的最多组数

难度: Hard

有一个甜甜圈商店，每批次都烤 batchSize 个甜甜圈。这个店铺有个规则，就是在烤一批新的甜甜圈时，之前所有甜甜圈都必须已经全部销售完毕。给你一个整数 batchSize 和一个整数数组 groups ，数组中的每个整数都代表一批前来购买甜甜圈的顾客，其中 groups[i] 表示这一批顾客的人数。每一位顾客都恰好只要一个甜甜圈。

当有一批顾客来到商店时，他们所有人都必须在下一批顾客来之前购买完甜甜圈。如果一批顾客中第一位顾客得到的甜甜圈不是上一组剩下的，那么这一组人都会很开心。

你可以随意安排每批顾客到来的顺序。请你返回在此前提下，最多有多少组人会感到开心。

示例 1：

输入：batchSize = 3, groups = [1,2,3,4,5,6]
输出：4
解释：你可以将这些批次的顾客顺序安排为 [6,2,4,5,1,3] 。那么第 1，2，4，6 组都会感到开心。

示例 2：

输入：batchSize = 4, groups = [1,3,2,5,2,2,1,6]
输出：4

提示：

1 <= batchSize <= 9
1 <= groups.length <= 30
1 <= groups[i] <= 10⁹

Submission

运行时间: 40 ms

内存: 17.1 MB

class Solution:
    def maxHappyGroups(self, batchSize: int, groups: List[int]) -> int:
        ans = 0
        freq = [0] * batchSize
        for g in groups:
            k = g % batchSize
            if k == 0:
                ans += 1
            elif freq[-k]:
                freq[-k] -= 1
                ans += 1
            else:
                freq[k] += 1
        
        @cache
        def dfs(left: int, cnt: Tuple[int]) -> int:
            res = 0
            cnt = list(cnt)
            for x, c in enumerate(cnt):
                if c:
                    cnt[x] -= 1
                    res = max(res, (left == 0) + dfs((left + x + 1) % batchSize, tuple(cnt)))
                    cnt[x] += 1
            return res
        return ans + dfs(0, tuple(freq[1:]))

Explain

该题解使用了贪心策略和深度优先搜索（DFS）结合记忆化递归的方法。首先，遍历所有顾客组，将每组顾客人数对batchSize取模后的余数记录在频率数组freq中，同时统计可以直接满足条件的组数（余数为0或者存在互补的余数对）。然后，使用记忆化的DFS来处理剩余的顾客组，尝试不同的顺序来最大化满足条件的组数。在DFS中，根据当前剩余的甜甜圈数量和各余数的频率，递归地探索不同的选择，并返回最大的满足条件的组数。

时间复杂度: O((batchSize - 1) ^ groups.length)

空间复杂度: O((batchSize - 1) ^ groups.length)

# class Solution:
#     def maxHappyGroups(self, batchSize: int, groups: List[int]) -> int:
#         ans = 0
#         freq = [0] * batchSize
#         for g in groups:
#             k = g % batchSize
#             if k == 0:
#                 ans += 1
#             elif freq[-k]:
#                 freq[-k] -= 1
#                 ans += 1
#             else:
#                 freq[k] += 1
#         
#         @cache
#         def dfs(left: int, cnt: Tuple[int]) -> int:
#             res = 0
#             cnt = list(cnt)
#             for x, c in enumerate(cnt):
#                 if c:
#                     cnt[x] -= 1
#                     res = max(res, (left == 0) + dfs((left + x + 1) % batchSize, tuple(cnt)))
#                     cnt[x] += 1
#             return res
#         return ans + dfs(0, tuple(freq[1:]))

Explore

在题解中，将每组顾客人数对batchSize取模的操作是为了简化问题。这是因为题目中涉及的是组数的最大化，而不是具体的顾客人数。通过取模操作，可以将问题转化为处理顾客组与batchSize的余数问题，这样就可以只关注余数，而不是具体的顾客数量。这种转化可以有效地减少问题的复杂度，因为处理的变量（余数）数量最多只有batchSize个。

互补的余数对是指两个数的余数和等于batchSize的一对值。例如，如果batchSize是5，那么余数1和4，余数2和3，以及余数0和5（如果有余数5的话）都是互补的余数对。在题解中，当检测到存在互补的余数对时，可以直接将这一对顾客组算作满足条件的组，因为它们加起来的总数正好是batchSize的倍数。这样做可以直接增加开心组数，因为每找到一对互补的余数对，就意味着有一组额外的顾客可以完全分配甜甜圈，从而增加满足条件的组数。

题解中的记忆化DFS是基于两个主要变量实现的：当前剩余的甜甜圈数量（left）和各余数的频率数组（cnt）。状态的记忆化是通过缓存已经计算过的(left, cnt)组合的结果来实现的。这种方法可以避免重复计算相同状态下的结果，从而大大提高算法的效率。每个状态代表了一个特定的余数组合以及相应的剩余甜甜圈数量，其结果表示从该状态开始可以额外满足的最大组数。

在DFS函数中，参数left表示当前剩余甜甜圈数量对batchSize的余数。它的主要作用是帮助判断加上当前选择的顾客组之后是否能形成一个完整的batchSize倍数，即是否能够形成一个新的满足条件的组。在递归过程中，通过更新left来模拟分配甜甜圈给当前选择的顾客组后的情况。如果在选择某个余数后left变为0，表示当前的选择可以使得总数达到batchSize的倍数，从而形成一个新的满足条件的组。这个参数对于决策过程至关重要，因为它直接影响了每一步选择后的状态和最终能够满足条件的组数。