题目描述

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

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

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

样例

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

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

限制

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

算法

(状态压缩动态规划) $O((n / m)^m \cdot m)$

1. 每个组中的人数在模去 $batchSize$ 后才有意义。统计出 $0$ 到 $batchSize$ 中，每一种余数出现的次数 $fre(i)$。显然 $fre(0)$ 可以直接加入到最终的答案中，接下来只考虑 $fre(1)$ 到 $fre(batchSize - 1)$。
2. 定义动态规划的状态为 $f(mask)$ 表示，当前使用的 $fre$ 的状态为 $mask$ 时，最多有多少次转移时的余数为 0。
3. 使用记忆化搜索，对于当前状态 $mask$，如果对应的 $fre(i) > 0$，则可以从 $fre(i) - 1$ 对应的 $mask_0$ 中转移。如果 $mask_0$ 的余数为 0，则转移 $f(mask) = \max(f(mask), f(mask_0) + 1)$。否则转移，$f(mask) = \max(f(mask), f(mask_0))$。
4. 最终答案为 $solve(mask) + fre(0)$。
5. 接下来需要分析如何从 $fre$ 数组映射到一个整数值状态 $mask$。（这里忽略 $fre(0)$）
6. 抽象来看，我们要将一个数组映射到一个整数。我们可以规定每一位的权重 $w$。即，$w(1) = 1$，$w(i) = w(i - 1) * (1 + fre(i - 1))$。
7. 正映射：$mask = fre(1) * w(1) + fre(2) * w(2) + \dots + fre(m - 1) * w(m - 1)$。
8. 逆映射：$fre(i) = mask \text{ mod } w(i + 1) / w(i)$。

时间复杂度

• 动态规划最多有 $O((n / m)^m)$ 个状态，每个状态需要 $O(m)$ 的时间转移，故总时间复杂度为 $O((n / m)^m \cdot m)$。其中 $m$ 为 $batchSize$。

空间复杂度

• 需要 $O((n / m)^m)$ 的额外空间存储状态。

C++ 代码

class Solution {
private:
    vector<int> w, f;

    int solve(int mask, int r, int m) {
        if (f[mask] != -1)
            return f[mask];

        int res = 0;
        for (int i = 1; i < m; i++) {
            if (mask % w[i + 1] / w[i] == 0) continue;

            int t = solve(mask - w[i], (r - i + m) % m, m);
            if (r == i) res = max(res, t + 1);
            else res = max(res, t);
        }

        return f[mask] = res;
    }

public:
    int maxHappyGroups(int batchSize, vector<int>& groups) {
        vector<int> fre(batchSize, 0);

        int r = 0;
        for (int g : groups) {
            fre[g % batchSize]++;
            r = (r + g) % batchSize;
        }

        w.resize(batchSize + 1);
        w[1] = 1;
        int mask = 0;
        for (int i = 2; i < batchSize + 1; i++) {
            w[i] = w[i - 1] * (fre[i - 1] + 1);
            mask += fre[i - 1] * w[i - 1];
        }

        f.resize(w[batchSize], -1);
        return solve(mask, r, batchSize) + fre[0];
    }
};