[数据结构与算法]Leetcode 526.优美的排列 二进制状压DP

题目链接：传送门

假设有从 1 到 N 的?N?个整数，如果从这?N?个数字中成功构造出一个数组，使得数组的第 i?位 (1 <= i <= N) 满足如下两个条件中的一个，我们就称这个数组为一个优美的排列。条件：

?（1）第?i?位的数字能被?i?整除
?（2）i?能被第 i 位上的数字整除
现在给定一个整数 N，请问可以构造多少个优美的排列？

题意：如字面意思构造一个排列，让第i位放的数字跟i是能够整除的一个关系。

思路：N<=15,从这个n的范围来看就是一个2的15次方的一个题目，排列的顾名思义，就是你在这个新构成的数组里边，每一个位置对应一个选择一个数字。那么我们直接用dp[i的二进制表示]当前选择的几个数字，一个基础的状态压缩dp问题。

二进制1的数量表示已经选择了几个数字

二进制1的位置表示选择的是数字几

dp[2] = (二进制)dp[010]? 表示选择了1个数，选了2这个数字

dp[4] = (二进制)dp[100]? 表示选择了1个数，选了3这个数字

dp[6] = (二进制)dp[110] 表示选择了两个数字，分别选择了2和3这两个数字

若dp[010]->dp[110] 表示选择第一个数字是2,选择第二个数字是3? :::? ?? [2]->[2,3]

若dp[100]->dp[110] 表示选择第一个数字是3,选择第二个数字是2? ?::? ? ?[3]->[3,2]

状态转换的方式就是这样，就是通过二进制的位运算来优化算法。

代码如下：

#include<algorithm>
const int maxn=(1<<15)+10;
int dp[maxn];
//统计1的个数，就是选择了几个数字
int one_num(int x){
    int ans=0;
    while(x){
        if(x&1) ans++;
        x>>=1;
    }
    return ans;
}
class Solution {
public:
    int countArrangement(int n) {
        dp[0]=1;
        for(int i=1;i<(1<<n);i++){
            dp[i]=0;
            for(int j=0;j<n;j++)
            {
                //选择了j这个数字
                if((i>>j)&1){
                    //一共选了多少个数字了，这就是对应选择的第几个数字
                    int pos=one_num(i);
                    //整除的这个关系判断一下
                    if(pos%(j+1)==0 || (j+1)%pos==0)
                        dp[i]+=dp[i^(1<<j)];
                }
            }
        }
        return dp[(1<<n)-1];
    }
};