状压dp使用二进制数来表示状态，将当前已选元素的集合表示为一个二进制数。
适用于需要枚举每一种排列进行判断、且最大的$n$有$10<n<20$的题目。
状压dp能使得时间复杂度从暴力搜索的$O(n!)$降到$O(n*2^n)$(相邻无关)或者$O(n^2 * 2^n)$(相邻相关)。

若当前表示已选元素的集合的二进制掩码为mask，则；

  1. mask &(1<<i) : 表示第i个元素是否被选择
  2. mask|(1<<i) : 表示将第i个元素加入集合
  3. popcount(mask) : 表示集合中元素的个数

1. 相邻无关

当前位置的选择不依赖于前一个位置的选择，只依赖于当前已选元素的集合。

$dp[mask]$表示状态为mask的情况(即已经选择的集合的二进制掩码为mask)下的最优解。

1.1 例题

假设有从 1 到 n 的 n 个整数。用这些整数构造一个数组 perm（下标从 1 开始），只要满足下述条件 之一 ，该数组就是一个 优美的排列 ：

  • perm[i] 能够被 i 整除
  • i 能够被 perm[i] 整除
  • 1 <= n <= 15

给你一个整数 n ，返回可以构造的 优美排列 的 数量 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int countArrangement(int n) {
        vector<int> dp(1 << n, 0);
        dp[0] = 1;
        for(int m = 0; m < 1 << n; ++m) {
            int l = popcount((unsigned) m);
            ++l;
            for(int j = 0; j < n; ++j) {
                int p = j + 1;
                if(!(m & (1<<j))){
                    if((l % p == 0)||(p % l == 0)){
                        dp[m | (1<<j)] += dp[m]; 
                    }
                }
            }
        }
        return dp.back();
    }

2. 相邻相关

当前位置的选择不仅依赖于当前已选元素的集合，还依赖于前一个位置的选择。

$dp[mask][i]$表示状态为mask、前一个位置的选择为i的情况下的最优解。

2.1 例题

给你一个下标从 0 开始的整数数组 nums ，它包含 n 个 互不相同 的正整数。如果 nums 的一个排列满足以下条件，我们称它是一个特别的排列：

  • 对于 0 <= i < n - 1 的下标 i ，要么 nums[i] % nums[i+1] == 0 ，要么 nums[i+1] % nums[i] == 0 。
  • 2 <= nums.length <= 14
  • 1 <= nums[i] <= 1e9

请你返回特别排列的总数目。由于答案可能很大，请将它对 $10^9 + 7$ 取余后返回。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
int specialPerm(vector<int>& nums) {
        const int mod = 1e9+7;
        int n=nums.size();
        vector<vector<int>>dp(1<<n,vector<int>(n,0));
        for(int i=0;i<n;++i){
            dp[1<<i][i]=1;
        }
        for(int m=0;m<1<<n;++m){
            for(int i=0;i<n;++i){
                if(m & (1<<i)){
                    for(int j=0;j<n;++j){
                        if(!(m&(1<<j))){
                            if((nums[i]%nums[j]==0)||(nums[j]%nums[i]==0)){
                                dp[m|(1<<j)][j]=(dp[m|(1<<j)][j] + dp[m][i])%mod;
                            }
                        }
                    }
                }
            }
        }
        int ans=0;
        for(int i=0;i<n;++i){
            ans=(ans+dp[(1<<n)-1][i])%mod;
        }
        return ans;
    }