题目描述
这是 LeetCode 上的 「526. 优美的排列」 ，难度为 「中等」。
Tag : 「位运算」、「状压 DP」、「动态规划」
示例1:
代码语言：javascript复制输入: 2
输出: 2
解释:
第 1 个优美的排列是 [1, 2]:
第 1 个位置（i=1）上的数字是1，1能被 i（i=1）整除
第 2 个位置（i=2）上的数字是2，2能被 i（i=2）整除
第 2 个优美的排列是 [2, 1]:
第 1 个位置（i=1）上的数字是2，2能被 i（i=1）整除
第 2 个位置（i=2）上的数字是1，i（i=2）能被 1 整除
说明:
- N是一个正整数，并且不会超过 15。
状态压缩 DP
利用数据范围不超过 15，我们可以使用「状态压缩 DP」进行求解。
使用一个二进制数表示当前哪些数已被选，哪些数未被选，目的是为了可以使用位运算进行加速。
我们可以通过一个具体的样例，来感受下「状态压缩」是什么意思：
例如 (000...0101)_2 代表值为 1和值为 3 的数字已经被使用了，而值为 2的节点尚未被使用。
然后再来看看使用「状态压缩」的话，一些基本的操作该如何进行：
假设变量 state存放了「当前数的使用情况」，当我们需要检查值为 k的数是否被使用时，可以使用位运算 a = (state >> k) & 1，来获取 state 中第 k 位的二进制表示，如果 a 为 1代表值为 k 的数字已被使用，如果为 0则未被访问。
代码：
代码语言：javascript复制class Solution {
public int countArrangement(int n) {
int mask = 1 << n;
int[][] f = new int[n 1][mask];
f[0][0] = 1;
for (int i = 1; i <= n; i ) {
// 枚举所有的状态
for (int state = 0; state < mask; state ) {
// 枚举位置 i（最后一位）选的数值是 k
for (int k = 1; k <= n; k ) {
// 首先 k 在 state 中必须是 1
if (((state >> (k - 1)) & 1) == 0) continue;
// 数值 k 和位置 i 之间满足任一整除关系
if (k % i != 0 && i % k != 0) continue;
// state & (~(1 << (k - 1))) 代表将 state 中数值 k 的位置置零
f[i][state] = f[i - 1][state & (~(1 << (k - 1)))];
}
}
}
return f[n][mask - 1];
}
}
状态压缩 DP（优化）
代码：
代码语言：javascript复制class Solution {
int getCnt(int x) {
int ans = 0;
while (x != 0) {
x -= (x & -x); // lowbit
ans ;
}
return ans;
}
public int countArrangement(int n) {
int mask = 1 << n;
int[] f = new int[mask];
f[0] = 1;
// 枚举所有的状态
for (int state = 1; state < mask; state ) {
// 计算 state 有多少个 1（也就是当前排序长度为多少）
int cnt = getCnt(state);
// 枚举最后一位数值为多少
for (int i = 0; i < n; i ) {
// 数值在 state 中必须是 1
if (((state >> i) & 1) == 0) continue;
// 数值（i 1）和位置（cnt）之间满足任一整除关系
if ((i 1) % cnt != 0 && cnt % (i 1) != 0) continue;
// state & (~(1 << i)) 代表将 state 中所选数值的位置置零
f[state] = f[state & (~(1 << i))];
}
}
return f[mask - 1];
}
}
- 时间复杂度：共有 2^n 的状态需要被转移，每次转移复杂度为 O(n)，整体复杂度为 O(n * 2^n)
- 空间复杂度：O(2^n)
总结
不难发现，其实两种状态压缩 DP 的思路其实是完全一样的。
只不过在朴素状压 DP 中我们是显式的枚举了考虑每一种长度的情况（存在维度 i），而在状压 DP（优化）中利用则 state中的
1的个数中蕴含的长度信息。
最后
这是我们「刷穿 LeetCode」系列文章的第 No.525 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。
在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：https://github.com/SharingSource/LogicStack-LeetCode 。
在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。
