LeetCode 526. 优美的排列

2026-09-13 HGNULB 约 4 分钟

文章信息 2 个分类 5 个标签

分类

LeetCode 中等

题目描述

✅ 526. 优美的排列

题意分析

将 $1$ 到 $n$ 各使用一次排成排列，使每个位置 position 与该位置的值 value 至少满足一种整除关系，统计合法排列数量。位置从 $1$ 开始，题目中 $n\le15$，可以用一个整数的二进制位表示已经使用的数字集合。

解法：按已用数字集合做状态压缩 DP

核心思路

[!blue]

mask 的第 value - 1 位为 $1$，表示这个数字已经使用。定义 dp[mask] 为：用这些数字填满前 bitCount(mask) 个位置，且这些位置全部合法的排列前缀数量。

相同集合可能对应不同顺序的前缀，但它们的已填位置数相同、剩余可用数字相同，之后的整除判断也只取决于新位置与新数字。因此可以把这些前缀的数量合并，未来再一起扩展，无需保存前缀的具体排列。

下一个位置是 position = bitCount(mask) + 1。枚举尚未使用的 value，满足 value % position == 0 或 position % value == 0 时，就把它接在所有当前合法前缀后面，执行 dp[mask | bit] += dp[mask]。

每个新前缀都能唯一拆成最后一个数字和此前的前缀，所以不同转移不会重复计算同一个排列。设置一个原本为零的二进制位，会让新掩码严格大于旧掩码，因此按掩码数值递增遍历时，所有前驱都已处理完毕。

解题步骤

创建长度为 1 << n 的计数数组，令 dp[0] = 1，表示空前缀只有一种。

依次枚举 mask，通过置位数确定下一个位置。

枚举 $1$ 到 $n$，跳过已使用数字，检查两种整除关系后累加到新集合状态。

返回全为一的掩码 (1 << n) - 1 对应的计数。完整集合已无可选数字，代码不会继续产生转移。

代码实现

class Solution {
    public int countArrangement(int n) {
        int[] dp = new int[1 << n];

        dp[0] = 1;

        for (int mask = 0; mask < dp.length; mask++) {
            int position = Integer.bitCount(mask) + 1;

            for (int value = 1; value <= n; value++) {
                int bit = 1 << (value - 1);

                if ((mask & bit) == 0 && (value % position == 0 || position % value == 0)) {
                    dp[mask | bit] += dp[mask];
                }
            }
        }

        return dp[dp.length - 1];
    }
}

import "math/bits"

func countArrangement(n int) int {
    dp := make([]int, 1<<n)
    dp[0] = 1
    for mask := range dp {
        position := bits.OnesCount(uint(mask)) + 1
        for value := 1; value <= n; value++ {
            bit := 1 << (value - 1)
            if mask&bit == 0 && (value%position == 0 || position%value == 0) {
                dp[mask|bit] += dp[mask]
            }
        }
    }
    return dp[len(dp)-1]
}

复杂度分析

时间复杂度：$O(n2^n)$，共有 $2^n$ 个集合状态，每个状态枚举 $n$ 个数字。

空间复杂度：$O(2^n)$，用于保存所有集合的方案数。

关键点总结

[!green]

状态保存已用数字集合，下一位置由集合大小唯一确定。

不同前缀顺序的数量通过累加保留，合并状态不会把它们当作同一个排列。

新集合数值严格增大，正序扫描就是有效的转移顺序。

易错点总结

[!yellow]

数值与位置从 $1$ 开始，二进制位从 $0$ 开始，value 对应 1 << (value - 1)。

两种整除关系满足至少一种即可，不能写成同时满足，也不能在两种都满足时重复加两次。

更新使用累加，不同前驱可能得到同一个已用集合。

dp[0] 必须为 $1$，否则没有任何方案能开始构造。

相似题目

题目	难度	关联与区别
46. 全排列	中等	从枚举所有排列出发，为当前位置增加整除限制，再用已选集合合并重复子问题。
52. N 皇后 II	困难	同样逐行或逐位置放置不同对象并计数，合法性由已占位置与额外约束决定。

转载与许可

作者 HGNULB

链接 https://hgnulb.github.io/blog/2026/80898241

许可本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！