LC.P526[优美的排列]

方法一：回溯

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    
    int n;
    boolean[] visited;

    public int countArrangement(int n) {
        this.n = n;
        visited = new boolean[n + 1];
        return dfs(1);
    }

    private int dfs(int i) {
        if (i > n) return 1;
        int ans = 0;
        for (int x = 1; x <= n; ++x) {
            if (!visited[x] && (x % i == 0 || i % x == 0)) {
                visited[x] = true;
                ans += dfs(i + 1);
                visited[x] = false;
            }
        }
        return ans;
    }
}
  • 时间复杂度：$O(n!)$
  • 空间复杂度：$O(n)$

方法二：回溯+状态压缩

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {

    int n;

    public int countArrangement(int n) {
        this.n = n;
        return dfs(1, 0);
    }

    private int dfs(int i, int visited) {
        if (i > n) return 1;
        int ans = 0;
        for (int x = 1; x <= n; ++x) {
            if ((((1 << x) & visited) == 0) && (x % i == 0 || i % x == 0)) {
                ans += dfs(i + 1, (1 << x) | visited);
            }
        }
        return ans;
    }
}
  • 时间复杂度：$O(n!)$
  • 空间复杂度：$O(n)$

方法三：回溯+记忆化搜索+状态压缩

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {

    int n;
    int[][] cache;

    public int countArrangement(int n) {
        this.n = n;
        cache = new int[n + 1][1 << n];
        return dfs(1, 0);
    }

    private int dfs(int i, int visited) {
        if (i > n) return 1;
        if (cache[i][visited] != 0) return cache[i][visited];
        int ans = 0;
        for (int x = 1; x <= n; ++x) {
            if ((((1 << x - 1) & visited) == 0) && (x % i == 0 || i % x == 0)) {
                ans += dfs(i + 1, (1 << x - 1) | visited);
            }
        }
        return cache[i][visited] = ans;
    }
}
  • 时间复杂度：$O(n!)$
  • 空间复杂度：$O(n \times 2^n)$

方法四：动态规划+状态压缩

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    
    public int countArrangement(int n) {
        int mask = 1 << n;
        int[][] dp = new int[n + 1][mask];
        dp[0][0] = 1;
        for (int i = 1; i <= n; ++i) {
            for (int visited = 0; visited < mask; ++visited) {
                if (Integer.bitCount(visited) == i) {
                    for (int x = 1; x <= n; ++x) {
                        if (((1 << (x - 1)) & visited) != 0 && (x % i == 0 || i % x == 0)) {
                            // i - 1位置没有放入x
                            // 1 << (x - 1) 表示第 x 位是1，取反就是这位是0，其他都是1
                            // 再与 visited 与运算表示打掉 visited 这位的 1
                            dp[i][visited] += dp[i - 1][visited & (~(1 << (x - 1)))];
                        }
                    }
                }
            }
        }
        return dp[n][mask - 1];
    }
}
  • 时间复杂度：$O(n^2 \times 2^n)$
  • 空间复杂度：$O(n \times 2^n)$

方法五：动态规划（优化）+状态压缩

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int countArrangement(int n) {
        int mask = 1 << n;
        int[] dp = new int[mask];
        dp[0] = 1;
        for (int visited = 0; visited < mask; ++visited) {
            int i = Integer.bitCount(visited);
            for (int x = 1; x <= n; ++x) {
                if (((1 << (x - 1)) & visited) != 0 && (x % i == 0 || i % x == 0)) {
                    // i - 1 位置没有放入x
                    dp[visited] += dp[visited & (~(1 << (x - 1)))];
                }
            }
        }
        return dp[mask - 1];
    }
}
  • 时间复杂度：$O(n \times 2^n)$
  • 空间复杂度：$O(2^n)$