前置知识：讲解003、讲解030、讲解031、讲解032、讲解033 位运算基础、根据数据量猜解法、双向广搜、从递归入手二维动态规划、状压dp-上
上节课 讲述了状压 dp 的原理和一些经典题目
本节课继续讲述 4 个状压 dp 问题，以及重要技巧：如何在位状态上，枚举所有子集的状态（题目4）
题目1.每个人戴不同帽子的方案数
题目描述
总共有 n 个人和 40 种不同的帽子，帽子编号从 1 到 40 。
给你一个整数列表的列表 hats ，其中 hats[i] 是第 i 个人所有喜欢帽子的列表。
请你给每个人安排一顶他喜欢的帽子，确保每个人戴的帽子跟别人都不一样，并返回方案数。
由于答案可能很大，请返回它对 10^9 + 7 取余后的结果。
提示：
n == hats.length1 <= n <= 101 <= hats[i].length <= 401 <= hats[i][j] <= 40hats[i]包含一个数字互不相同的整数列表。
测试链接
思路
看数据量：帽子数量是 40，人数是 10，所以要用人做 status 位信息，状压 dp 数据量说明
答案
const (
MOD = 1e9 + 7
)
var (
m int // 帽子编号的最大值，1~m
n int // 人数，0~n-1
hats []int // 1~m 帽子，能满足哪些人，位状态（0 位不用）
cache [][]int // cache[s][i]: 所有人戴好帽子的状态 s 下，来到 i 号帽子，方案数
)
func numberWays(arr [][]int) int {
m = 0
for _, person := range arr {
for _, hat := range person {
m = max(m, hat)
}
}
n = len(arr)
hats = make([]int, m+1)
for i, person := range arr {
for _, hat := range person {
hats[hat] |= 1 << i
}
}
cache = make([][]int, 1<<n)
for i := range cache {
cache[i] = make([]int, m+1)
for j := range cache[i] {
cache[i][j] = -1
}
}
return f(0, 1)
}
// status：0~n-1 的人，0：没戴好帽子；1：戴好了帽子
// idx：来到了 idx 号帽子
// 返回：有多少种方法
func f(status, idx int) int {
// 所有人都戴好了帽子
if status == 1<<n-1 {
return 1
}
// 帽子用完了，还有人没戴好帽子
if idx == m+1 {
return 0
}
if cache[status][idx] != -1 {
return cache[status][idx]
}
// 可能性 1：当前 idx 号帽子，不分配给任何人
ans := f(status, idx+1)
// 可能性 2：当前 idx 号帽子，分配给可能的每一个人
for i := 0; i < n; i++ {
// i 号人喜欢这个帽子，并且 i 号人没戴好帽子
if hats[idx]&(1<<i) != 0 && status&(1<<i) == 0 {
ans = (ans + f(status|(1<<i), idx+1)) % MOD
}
}
cache[status][idx] = ans
return ans
}遍历当前 idx 号帽子，分配给可能的每一个人时，可以不要遍历所有人，而是提取出二进制状态中最右侧的 1（Brian Kernighan 算法），获得喜欢该帽子的人即可
// 可能性 1：当前 idx 号帽子，不分配给任何人
ans := f(status, idx+1)
// 可能性 2：当前 idx 号帽子，分配给可能的每一个人
// for i := 0; i < n; i++ {
// // i 号人喜欢这个帽子，并且 i 号人没戴好帽子
// if hats[idx]&(1<<i) != 0 && status&(1<<i) == 0 {
// ans = (ans + f(status|(1<<i), idx+1)) % MOD
// }
// }
cur := hats[idx]
rightOne := 0
for cur != 0 {
rightOne = cur & -cur
if status&rightOne == 0 {
ans = (ans + f(status|rightOne, idx+1)) % MOD
}
cur ^= rightOne
}复杂度
- 时间复杂度：， 是帽子编号的最大值
- 遍历所有人：每个格子枚举代价是
- Brian Kernighan 算法：每个格子枚举代价是每个帽子被人喜欢的平均人数，小于等于
- 空间复杂度：，即二维 dp 表大小
题目2.最优账单平衡
题目描述
给你一个表示交易的数组 transactions
其中 transactions[i] = [fromi, toi, amounti] 表示 ID = fromi 的人给 ID = toi 的人共计 amounti
请你计算并返回还清所有债务的最小交易笔数
如：有 4 个人，经过多笔交易后的债务表为 [-2, -6, -2, 10]，则答案是 3，即最后一人分别给前三个人还债务
问题相当于：输入一个不包含 0 的数组，该数组累加和等于 0，求将所有数字还债成 0 的最小交易笔数
数据规模：
0 <= 人员编号 <= 12
测试链接
思路
将数组划分成 k 堆，每堆的累加和要为 0，且是最小单元（不可再被分割），每一堆的交易笔数就是这堆数的数量减一
相当于将问题转化成：将数组划分成累加和为 0 且不可再被分割的 k 堆，求 k 的最大值
答案就是：n-k，n 是原数组长度
答案
const (
MAXN = 13
)
var (
arr []int
n int
cache []int
)
func minTransfers(transactions [][]int) int {
build(transactions)
n = len(arr)
cache = make([]int, 1<<n)
for i := range cache {
cache[i] = -1
}
return n - f(1<<n-1, 0)
}
func build(transactions [][]int) {
help := make([]int, MAXN)
for _, item := range transactions {
help[item[0]] -= item[2]
help[item[1]] -= item[2]
}
arr = []int{}
for _, num := range help {
if num != 0 {
arr = append(arr, num)
}
}
}
// status：当前集合中有哪些元素位信息，0：没有；1：有
// sum：当前集合累加和
// 集合拆分出累加和是 0 的不可拆分小集合的最大数量
func f(status, sum int) int {
if cache[status] != -1 {
return cache[status]
}
ans := 0
if status&(status-1) != 0 { // 集合中不止一个元素
if sum == 0 {
for i := 0; i < n; i++ {
if status&(1<<i) != 0 {
// 找到任何一个元素，去除这个元素
// 剩下的集合进行尝试，返回值 +1
ans = f(status^(1<<i), sum-arr[i]) + 1
// 然后不需要再尝试下一个元素了，因为答案一定是一样的
// 所以直接 break
break
}
}
} else {
for i := 0; i < n; i++ {
if status&(1<<i) != 0 {
ans = max(ans, f(status^(1<<i), sum-arr[i]))
}
}
}
}
cache[status] = ans
return ans
}复杂度
- 时间复杂度：
- 大部分题解的时间复杂度 ，不是最优解，不再讲述
- 空间复杂度：