526. 优美的排列

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

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

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

示例 1：

1
2
3
4
5
6
7
8
9
输入：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：

1
2
输入：n = 1
输出：1

提示：

  • 1 <= n <= 15

递归，vis数组记录状态

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int countArrangement(int n) {
        return dfs(1, new int[n]);
    }
    public int dfs(int cur, int[] vis) {
        int n = vis.length, res = 0;
        if (cur == n+1) return 1;
        for (int i = 0; i < n; i++) {
            if (vis[i] == 1) continue;
            if ((i+1) % cur != 0 && cur % (i+1) != 0) continue;
            vis[i] = 1;
            res += dfs(cur+1, vis);
            vis[i] = 0;
        }
        return res;
    }
}

递归，用一个int记录状态

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public int countArrangement(int n) {
        return dfs(1, 0, n);
    }
    public int dfs(int cur, int vis, int n) {
        int res = 0;
        if (cur == n+1) return 1;
        for (int i = 0; i < n; i++) {
            if ((vis & (1<<i)) > 0) continue;
            if ((i+1) % cur != 0 && cur % (i+1) != 0) continue;
            res += dfs(cur+1, vis | (1<<i), n);
        }
        return res;
    }
}

状压dp，记忆化搜索，用一个int记录状态

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int countArrangement(int n) {
        int[] memo = new int[1<<n];
        Arrays.fill(memo, -1);
        return dfs(1, 0, n, memo);
    }
    public int dfs(int cur, int vis, int n, int[] memo) {
        int res = 0;
        if (memo[vis] != -1) return memo[vis];
        if (cur == n+1) return 1;
        for (int i = 0; i < n; i++) {
            if ((vis & (1<<i)) > 0) continue;
            if ((i+1) % cur != 0 && cur % (i+1) != 0) continue;
            res += dfs(cur+1, vis | (1<<i), n, memo);
        }
        return memo[vis] = res;
    }
}

状压dp，递推，用一个int记录状态

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int countArrangement(int n) {
        // f[s]: 当前访问到的这些bit的状态下，优美排列的数量
        int[] f = new int[1<<n];
        f[(1<<n)-1] = 1;  // 访问到所有bit的状态，记录为1
        for (int s = (1<<n)-1; s >= 0; s--) {  // 从后往前遍历
            for (int i = 0; i < n; i++) {  // 遍历每一个可能的bit
                if ((s & (1<<i)) > 0) continue;  // 已访问，跳过
                int cur = Integer.bitCount(s) + 1;  // 上一状态bit为1的数量
                if (cur%(i+1) != 0 && (i+1)%cur != 0) continue;
                f[s] += f[s|(1<<i)];
            }
        }
        return f[0];
    }
}