前置知识: 讲解003、讲解030、讲解031、讲解032、讲解033 - 位运算基础算法 讲解043 - 根据数据量猜解法的技巧，天字第一号重要技巧 讲解063 - 双向广搜 讲解067 - 从递归入手二维动态规划 讲解080 - 状压dp-上 【必备】课程的动态规划大专题从讲解066开始，建议从头开始学习会比较系统

上节课讲述了状压dp的原理和一些经典题目 本节课继续讲述4个状压dp问题，以及重要技巧：如何在位状态上，枚举所有子集的状态（题目4）

注意： 轮廓线dp是状压dp中一类比较难的问题，【扩展】课程阶段讲述 插头dp是轮廓线dp中一类更难的问题，在笔试、面试中几乎没有出现的可能，不会安排。比赛同学自行学习

题目1 每个人戴不同帽子的方案数 总共有 n 个人和 40 种不同的帽子，帽子编号从 1 到 40 给你一个整数列表的列表 hats ，其中 hats[i] 是第 i 个人所有喜欢帽子的列表 请你给每个人安排一顶他喜欢的帽子，确保每个人戴的帽子跟别人都不一样，并返回方案数 由于答案可能很大，请返回它对10^9+7取余后的结果 测试链接 : https://leetcode.cn/problems/number-of-ways-to-wear-different-hats-to-each-other

题目2 最优账单平衡 给你一个表示交易的数组 transactions 其中 transactions[i] = [fromi, toi, amounti] 表示 ID = fromi 的人给 ID = toi 的人共计 amounti 请你计算并返回还清所有债务的最小交易笔数 测试链接 : https://leetcode.cn/problems/optimal-account-balancing/

注意： 大部分题解的时间复杂度O(3^n)，这不是最优解，不再讲述 最优解的时间复杂度O(2^n * n)，也就是课上讲的解法

题目3 好子集的数目 给你一个整数数组 nums，好子集的定义如下： nums的某个子集，所有元素的乘积可以表示为一个或多个互不相同质数的乘积 比如nums = [1, 2, 3, 4] [2, 3]，[1, 2, 3]，[1, 3] 是好子集 乘积分别为6=23，6=23，3=3 [1, 4]和[4]不是好子集，因为乘积分别为4=22和4=22 请你返回nums中不同的好子集的数目对10^9+7取余的结果 如果两个子集拥有的下标不同，那么它们被视为不同的子集 测试链接 : https://leetcode.cn/problems/the-number-of-good-subsets/

题目4 分配重复整数 给你一个长度为n的整数数组nums，这个数组中至多有50个不同的值 同时你有m个顾客的订单quantity，其中整数quantity[i]是第i位顾客订单的数目 请你判断是否能将nums中的整数分配给这些顾客，且满足： 第i位顾客恰好有quantity[i]个整数、第i位顾客拿到的整数都是相同的 每位顾客都要满足上述两个要求，返回是否能都满足 测试链接 : https://leetcode.cn/problems/distribute-repeating-integers/

不能用贪心的例子 : nums = [1,1,2,2,1]、quantity = [2,2,1]

j枚举了status的所有子集状态，建议直接记住 for (int j = status; j > 0; j = (j - 1) & status) { .. }

题目4的时间复杂度分析

时间复杂度 O(n * 3的m次方)，n不用说了，可变参数index的变化范围，那后面的3的m次方怎么来的？ 元素个数为m的集合: 其中挑选0个元素组成子集，数量为C(m,0)，这个子集去枚举它的所有子集，枚举代价2的0次方 其中挑选1个元素组成子集，数量为C(m,1)，这个子集去枚举它的所有子集，枚举代价2的1次方 . . . 其中挑选k个元素组成子集，数量为C(m,k)，这个子集去枚举它的所有子集，枚举代价2的k次方 . . . 其中挑选m个元素组成子集，数量为C(m,m)，这个子集去枚举它的所有子集，枚举代价2的m次方 把上面都加起来，总和 =

3的m次方 = (1+2)的m次方，把(1+2)的m次方根据二项式定理展开，就能得到上面的式子

—— 本文来自火龙信奥（义乌睿码科技）：义乌青少年信息学奥赛与编程教育平台，专注 CSP-J/S、NOIP、GESP 竞赛培训，线上线下融合教学，助力编程升学。网址：hlcoding.com