题目截图

题目分析

• 暴力解法就是2 ** n可能会超时
• 但是先1后2和先2后1对后面的结果是一样的，因此可以考虑记忆化cache
• 每次的操作就是取一个，因此需要考虑两个变量
• 一是当前的总余数cur，另一个是剩下可取的cnt表用tuple
• 由于是mod操作，可以先全部mod batchsize
• res记录当前所有可能的最大值
• 找到可以取的下一个值，res = max(res, tmp + (cur == 0))
• tmp = dfs((cur + i) % batchsize, tuple(lst))
• 记得回溯即可

ac code

class Solution:
    def maxHappyGroups(self, batchSize: int, groups: List[int]) -> int:
        # 这个东西看起来很像位运算...
        # 让最多的组的轮到第一个人的余数为0
        
        cnt = [0] * batchSize
        for num in groups:
            cnt[num % batchSize] += 1

        # 先1后2 和 先2后1 对后面没有区别
        # 所以可以考虑记忆话搜索，记录剩余的状态（当前余数，剩余可取个数）
        # status可用二进制替代和优化
        # 遍历下一个能取的值
        # 0先排在前面！不在dfs中考虑
        @cache
        def dfs(cur, status):
            lst = list(status)
            res = 0 # 记录最多的结果
            # i -> 人数, v -> 剩余个数
            for i, v in enumerate(lst, 1):
                if v:
                    lst[i - 1] -= 1
                    # dfs
                    res = max(res, (cur == 0) + dfs((cur + i) % batchSize, tuple(lst)))
                    # 回溯
                    lst[i - 1] += 1
            return res
        
        return cnt[0] + dfs(0, tuple(cnt[1:]))

java 记忆化学习

class Solution {
    // 每个状态不可能超过30个，可以用5位完全存储状态(2进制度)
    // 共9个状态, 9 * 5 = 45 < 64 可以用long解决
    // aaaaabbbbb....kkkkk(连续的5位记录一个状态)
    static final int K_WIDTH = 5;
    static final int K_WIDTH_MASK = (1 << K_WIDTH) - 1;

    public int maxHappyGroups(int batchSize, int[] groups) {
        // 用cnt记录个数
        int[] cnt = new int[batchSize];
        for (int x : groups) {
            ++cnt[x % batchSize];
        }

        // 把cnt转化成位运算记录（faster）
        long start = 0;
        for (int i = batchSize - 1; i >= 1; --i) {
            start = (start << K_WIDTH) | cnt[i];
        }

        Map<Long, Integer> memo = new HashMap<Long, Integer>();

        // memo是引用类型，put了之后就马上改变！
        return dfs(memo, batchSize, start) + cnt[0];
    }

    public int dfs(Map<Long, Integer> memo, int batchSize, long mask) {
        if (mask == 0) {
            return 0;
        }

        if (!memo.containsKey(mask)) {
            long total = 0;
            // 计算当前状态对应的总数
            for (int i = 1; i < batchSize; ++i) {
                long amount = ((mask >> ((i - 1) * K_WIDTH)) & K_WIDTH_MASK);
                total += i * amount;
            }

            int best = 0;
            for (int i = 1; i < batchSize; ++i) {
                long amount = ((mask >> ((i - 1) * K_WIDTH)) & K_WIDTH_MASK);
                if (amount > 0) {
                    // 取其中一个可取的状态
                    int result = dfs(memo, batchSize, mask - (1L << ((i - 1) * K_WIDTH)));
                    // 若达到条件，结果+1
                    if ((total - i) % batchSize == 0) {
                        ++result;
                    }
                    best = Math.max(best, result);
                }
            }

            memo.put(mask, best);
        }
        return memo.get(mask);
    }
}

总结

• 一道很经典的记录当前值 + 剩余状态可取值的dfs记忆化操作
• 看到数据范围就可以考虑py的cache，也可以进一步用位运算优化！