526-优美的排列(Beautiful Arrangement)

原文链接: https://leetcode-cn.com/problems/beautiful-arrangement

英文原文

Suppose you have n integers labeled 1 through n. A permutation of those n integers perm (1-indexed) is considered a beautiful arrangement if for every i (1 <= i <= n), either of the following is true:

perm[i] is divisible by i.
i is divisible by perm[i].

Given an integer n, return the number of the beautiful arrangements that you can construct.

Example 1:

Input: n = 2
Output: 2
Explanation: 
The first beautiful arrangement is [1,2]:
    - perm[1] = 1 is divisible by i = 1
    - perm[2] = 2 is divisible by i = 2
The second beautiful arrangement is [2,1]:
    - perm[1] = 2 is divisible by i = 1
    - i = 2 is divisible by perm[2] = 1

Example 2:

Input: n = 1
Output: 1

Constraints:

1 <= n <= 15

中文题目

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

perm[i] 能够被 i 整除
i 能够被 perm[i] 整除

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

示例 1：

输入：n = 2
输出：2
解释：
第 1 个优美的排列是 [1,2]：
    - perm[1] = 1 能被 i = 1 整除
    - perm[2] = 2 能被 i = 2 整除
第 2 个优美的排列是 [2,1]:
    - perm[1] = 2 能被 i = 1 整除
    - i = 2 能被 perm[2] = 1 整除

示例 2：

输入：n = 1
输出：1

提示：

1 <= n <= 15

通过代码

高赞题解

状态压缩 DP

利用数据范围不超过 $15$，我们可以使用「状态压缩 DP」进行求解。

使用一个二进制数表示当前哪些数已被选，哪些数未被选，目的是为了可以使用位运算进行加速。

我们可以通过一个具体的样例，来感受下「状态压缩」是什么意思：

例如 $(000…0101)_2$ 代表值为 $1$ 和值为 $3$ 的数字已经被使用了，而值为 $2$ 的节点尚未被使用。

然后再来看看使用「状态压缩」的话，一些基本的操作该如何进行：

假设变量 $state$ 存放了「当前数的使用情况」，当我们需要检查值为 $k$ 的数是否被使用时，可以使用位运算 a = (state >> k) & 1，来获取 $state$ 中第 $k$ 位的二进制表示，如果 a 为 $1$ 代表值为 $k$ 的数字已被使用，如果为 $0$ 则未被访问。

定义 $f[i][state]$ 为考虑前 $i$ 个数，且当前选择方案为 $state$ 的所有方案数量。

一个显然的初始化条件为 $f[0][0] = 1$，代表当我们不考虑任何数（$i = 0$）的情况下，一个数都不被选择（$state = 0$）为一种合法方案。

不失一般性的考虑 $f[i][state]$ 该如何转移，由于本题是求方案数，我们的转移方程必须做到「不重不漏」。

我们可以通过枚举当前位置 $i$ 是选哪个数，假设位置 $i$ 所选数值为 $k$，首先 $k$ 值需要同时满足如下两个条件：

$state$ 中的第 $k$ 位为 $1$；
要么 $k$ 能被 $i$ 整除，要么 $i$ 能被 $k$ 整除。

那么根据状态定义，位置 $i$ 选了数值 $k$，通过位运算我们可以直接得出决策位置 $i$ 之前的状态是什么：$state & (\lnot (1 << (k - 1)))$，代表将 $state$ 的二进制表示中的第 $k$ 位置 $0$。

最终的 $f[i][state]$ 为当前位置 $i$ 选择的是所有合法的 $k$ 值的方案数之和：

$$
f[i][state] = \sum_{k = 1}^{n} f[i - 1][state & (\lnot (1 << (k - 1)))]
$$

一些细节：由于给定的数值范围为 $[1,n]$，但实现上为了方便，我们使用 $state$ 从右往左的第 $0$ 位表示数值 $1$ 选择情况，第 $1$ 位表示数值 $2$ 的选择情况 … 即对选择数值 $k$ 做一个 $-1$ 的偏移。

代码：

[]
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];
    }
}

时间复杂度：共有 $n * 2^n$ 的状态需要被转移，每次转移复杂度为 $O(n)$，整体复杂度为 $O(n^2 * 2^n)$
空间复杂度：$O(n * 2^n)$

状态压缩 DP（优化）

通过对朴素的状压 DP 的分析，我们发现，在决策第 $i$ 位的时候，理论上我们应该使用的数字数量也应该为 $i$ 个。

但这一点在朴素状压 DP 中并没有体现，这就导致了我们在决策第 $i$ 位的时候，仍然需要对所有的 $state$ 进行计算检查（即使是那些二进制表示中 $1$ 的出现次数不为 $i$ 个的状态）。

因此我们可以换个思路进行枚举（使用新的状态定义并优化转移方程）。

定义 $f[state]$ 为当前选择数值情况为 $state$ 时的所有方案的数量。

这样仍然有 $f[0] = 1$ 的初始化条件，最终答案为 $f[(1 << n) - 1]$。

不失一般性考虑 $f[state]$ 如何计算：

从当前状态 $state$ 进行出发，检查 $state$ 中的每一位 $1$ 作为最后一个被选择的数值，这样仍然可以确保方案数「不重不漏」的被统计，同时由于我们「从小到大」对 $state$ 进行枚举，因此计算 $f[state]$ 所依赖的其他状态值必然都已经被计算完成。

同样的，我们仍然需要确保 $state$ 中的那一位作为最后一个的 $1$ 需要与所放的位置成整除关系。

因此我们需要一个计算 $state$ 的 $1$ 的个数的方法，这里使用 $lowbit$ 实现即可。

最终的 $f[state]$ 为当前位置选择的是所有合法值的方案数之和：

$$
f[state] = \sum_{i = 0}^{n}f[state & ( \lnot (1 << i))]
$$

代码：

[]
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$ 的个数中蕴含的长度信息。

最后

如果有帮助到你，请给题解点个赞和收藏，让更多的人看到 ~ (“▔□▔)/

也欢迎你关注我（公主号后台回复「送书」即可参与长期看题解学算法送实体书活动）或加入「组队打卡」小群，提供写「证明」&「思路」的高质量题解。

所有题解已经加入刷题指南，欢迎 star 哦 ~

统计信息

通过次数	提交次数	AC比率
34292	46663	73.5%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言

相似题目

题目	难度
优美的排列 II	中等

凤起丶宛南

从来没有真正的绝境，只有心灵的迷途