子集和 DP - 模板详解

子集遍历

问题

使用二进制表示一个集合，10100表示集合包含2个元素，有时我们需要遍历该集合的非空子集，10100对应的非空子集有10100、10000、00100。

模板

// 遍历 u 的非空子集
for (int s = u; s; s = (s - 1) & u) {
  // s 是 u 的一个非空子集
}
1
2
3
4

分析

每次将s更新为(s - 1) & u，每次减1是将s中位最低的1去除掉，按位与是保证s中1只出现在u中对应位为1的位置，遍历10100的过程如下

1: 10100
2: (10100 - 1) & 10100 = 10011 & 10100 = 10000
3：(10000 - 1) & 10100 = 01111 & 10100 = 00100
4: (00100 - 1) & 10100 = 00011 & 10100 = 00000 // 结束
1
2
3
4

时间复杂度：设二进制u 中 1 的个数为m，用这种方法可以在 2 ^ m的时间复杂度内遍历u的子集（因为u一共有2 ^ m个子集）。进而可以在 3 ^ n的时间复杂度内遍历大小为n的集合的每个子集的子集。（复杂度为3 ^ n 是因为每个元素都有不在大子集中/只在大子集中/同时在大小子集中 三种状态。

SOS DP

问题

用一个二进制数表示一个集合，每个集合对应一个值，a[i]就表示集合i对应的值。

需求：统计一个集合的所有子集对应的值（例如统计该集合所有子集对应值之和）。

朴素思路：利用上面讲到的知识，遍历该集合对应的所有子集，在遍历的过程中统计答案。对于大量查询往往会超时。

SOS DP：子集和 DP，f[i] 表示集合i对应的所有子集的值的统计结果。

模板

SOS DP (Sum of Subset)，子集和 DP。a[i] 表示集合i对应的值，f[i]表示集合i的所有子集对应值之和，下面代码就是用于求解f[]

// 遍历所有的集合，并初始化
for (int i = 0; i < (1 << n); i++) f[i] = a[i];

for (int k = 0; k < n; k++)
    for (int i = 0; i < (1 << n); i++) { // 遍历所有集合
	    if(i & (1 << k))
            f[i] += f[i ^ (1 << k)];
}
1
2
3
4
5
6
7
8

分析

以上代码是降维后的写法，为了方便理解，我们先看看二维代码该如何写。

a[i] 表示集合i对应的值，f[i]表示集合i的所有子集对应值之和，dp[i][k] 表示集合i，仅改变最低k位（最靠右的k位，k = 0 表示最低位）形成的子集对应值之和，求f[i]，设集合共n位，则 f[i] = dp[i][n - 1]，其中dp[i][n - 1]表示仅修改下标在[0, n - 1] 的二进制位形成的子集对应值之和，此时就是能修改所有位，因此想求f[]就需要求dp[][n - 1]。接下来我们看看如何求解dp[][]。

// 此处 -1 仅仅用于示意，表示初始化
for (int i = 0; i < (1 << n); i++) dp[i][-1] = a[i];

for (int i = 0; i < (1 << n); i++) {
    for (int k = 0; k < n; k++) {
        if (i & (1 << k)) // 集合 i 的第 k 位为 1
            dp[i][k] = dp[i][k - 1] + dp[i ^ (1 << k)][k - 1];
        else // 集合 i 的第 k 位为 0
            dp[i][k] = dp[i][k - 1];
    }
    f[i] = dp[i][n - 1];
}
1
2
3
4
5
6
7
8
9
10
11
12

上面代码首先遍历所有集合，用a[i]初始化dp[i][-1]，-1仅仅用于示意，表示不修改任何二进制位形成的子集，也就是它自身，因此直接初始化为a[i]。

然后是两层循环，外层循环按二进制值从小到大遍历所有的集合，内层循环从小到大遍历k。

已知 dp[][k - 1] 如何求 dp[][k] 呢 ？注意到，一个集合的子集是通过将原集合某些为1的位改为0形成的，因此也只能通过修改为1的位才能形成新子集。我们根据集合i的第k位的值分类讨论：

情况一：集合i第k位为0

即i & (1 << k)值为0。此时不能通过修改第k位，形成新子集，只能通过修改下标在[0, k - 1] 范围内的1形成子集，这不就是dp[i][k - 1]对应的值吗？因此此时是dp[i][k] = dp[i][k - 1]

情况二：集合i第k位为1

即i & (1 << k)值为1。此时有两种选择，不修改当前位、将当前位修改为0。

• 不修改当前位，也就是仅修改[0, k - 1]范围内的位，其值为dp[i][k - 1]。
• 修改当前位，从1变为0，此时对应的二进制值变为i ^ (1 << k)，此时还可以通过修改[0, k - 1]范围内的位形成新子集，那么对应的值便为dp[i ^ (1 << k)][k - 1]

因此这种情况下dp[i][k] = dp[i][k - 1] + dp[i ^ (1 << k)][k - 1]。

知道二维代码的写法，现在思考一下，dp[][]数组是否可以省略掉，直接更新f[]呢？

// 遍历所有的集合，并初始化
for (int i = 0; i < (1 << n); i++) f[i] = a[i];

for (int k = 0; k < n; k++)
    for (int i = 0; i < (1 << n); i++) { // 遍历所有集合
	    if(i & (1 << k))
            f[i] += f[i ^ (1 << k)];
}
1
2
3
4
5
6
7
8

现在我们就来分析省略dp[][]的写法。代码首先遍历所有集合，f[i] = a[i] 表示不修改集合i的任何位形成的子集对应的值之和（此时即为集合自身）。

然后是两层循环，外层循环从小到大遍历k，此时f[i]表示修改集合i位于[0, k]的位形成的子集对应的值之和，当外层循环结束，f[i]对应的值就是我们需要求的。内层循环，从小到大遍历所有集合，如果集合i的第k位为1则f[i] += f[i ^ (1 << k)]。

设当前的遍历位置为外层循环k，内层循环i，此时正在求f[i]的值，我们分析一下此时此刻，f[]对应的值是哪个阶段的。f[0] ~ f[i - 1] 已经更新过了，因此保存的是k阶段的值，f[i] ~ f[(1 << n) - 1]正在等待更新，因此保存的是k - 1阶段的值。

当集合i的第k位为0时，保持f[i]的值不变，即对应上面代码中的dp[i][k] = dp[i][k - 1]。

当集合i的第k位为1时，f[i] += f[i ^ (1 << k)]，因为i ^ (1 << k)小于i（去掉了1），因此f[i ^ (1 << k)]在当前轮已经更新过了，它保存的是k阶段的值，f[i]还没更新，保存的是k - 1阶段的值，那么这条更新语句对应的代码为dp[i][k] = dp[i][k - 1] + dp[i ^ (1 << k)][k]。等等，怎么感觉不对？后面部分不应该是+ dp[i ^ (1 << k)][k - 1] 吗，仔细一想，i ^ (1 << k)的第k位为0，那么dp[i ^ (1 << k)][k] = dp[i ^ (1 << k)][k - 1]，因此上面的更新是 OK 的。

至此，分析完毕，可以快乐地做题了。

等等。还有一件事！！！

f[i] 表示的是i的所有子集对应的值之和，如果题目让你求以i为子集的所有集合之和该怎么办？其实很简单，将更新语句代码顺序换一下即可。

// 遍历所有的集合，并初始化
for (int i = 0; i < (1 << n); i++) f[i] = a[i];

for (int k = 0; k < n; k++)
    for (int i = 0; i < (1 << n); i++) { // 遍历所有集合
	    if(i & (1 << k))
            f[i ^ (1 << k)] += f[i]; // i ^ (1 << k) 是 i 的子集，因此将 f[i] 加到前者
}
1
2
3
4
5
6
7
8