HJ143好排列计数：状态压缩与记忆化DFS的完整解法

HJ143 这道题标题里三个关键词HJ、小红、好排列。HJ 是机考题库里的题号前缀143 是题号小红是题面里的主人公这类题在笔试和算法面试里非常典型。题面本身不复杂核心一句话统计满足整除关系的排列数量。但真上手写代码你会发现它同时考了三件事——能不能从暴力枚举里跳出来会不会用状态压缩表达“哪些位置已经被占用”以及能不能抓住整除关系带来的结构性规律。这篇文章我就把这道题的完整解法、代码实现和踩坑过程拆开讲适合正在准备机考笔试的人也适合想练熟 DFS 加记忆化这套套路的人。1. 题目到底在说什么动手前先把题面读透1.1 题面还原与核心定义题面的常见版本是这样的小红定义一个长度为 n 的排列 p也就是 1 到 n 每个数字恰好出现一次是“好排列”当且仅当对每个位置 i注意是 1 到 n 的下标不是从 0 开始都满足 p[i] 能被 i 整除或者 i 能被 p[i] 整除。两个条件满足其中一个就算合法用代码写就是p[i] % i 0 || i % p[i] 0。输入一个整数 n输出好排列的总数。这个“或者”很关键。很多人一上来会顺手写成“且”这是第一个大坑。举个例子n2 时排列 [2,1]位置 1 放数字 2因为 2%10 所以合法位置 2 放数字 1因为 2%10 也合法两个位置都满足这是个好排列。如果写成“且”位置 1 的 2 既不满足 2%1满足但如果换成别的数字就会出问题。所以先把这个条件抠死。另外要强调这不是让你构造一个合法排列而是统计一共有多少个。输出是“数量”不是排列本身。这个区别决定了算法方向构造题可以贪心、回溯找一条路计数题得把整个搜索树跑完还要防止重复计算。1.2 先算一笔账暴力枚举为什么必须死不懂套路的人会怎么写生成 1 到 n 的全排列逐个判断是否满足条件。n10 的时候有 3628800 个排列n12 直接到 479001600n15 就破万亿了。机考环境里 n12 纯暴力基本跑不完全排列递归本身的开销还不算在内。所以别想着“反正数据小暴力莽一把”这题的数据范围就是为了逼你用状态压缩。核心矛盾在于排列数量是指数级增长的但“好排列”的条件实际上很稀疏——每个位置只接受少数几个数字。比如 n20 时位置 13 只能放 1 或者 13因为 13 是质数其他数字和 13 既没有倍数关系也没有约数关系。你想想一个位置只剩两个候选这搜索空间天然就小。所以我的第一反应是把视角从“数字在哪个位置”切换成“每个数字可以去哪些位置”。前者是排列的常规视角后者才是计数题的破局点。能剪枝就剪枝能记忆化就记忆化这题的性价比方案就是 DFS 加状态压缩。2. 破局关键把“排列”看成“给每个数字排位置”2.1 候选位置表一切从整除关系出发好排列的判定条件等价于数字 x 放在位置 i 上必须有 x 能被 i 整除或者 i 能被 x 整除。翻译成人话数字 x 能放的位置只有两类i 是 x 的约数或者 i 是 x 的倍数且 i 不超过 n。以 n4 为例手动列一下每个数字能去的位置数字可放位置数量11、2、3、4421、2、4331、3241、2、43看出规律没有数字 1 最自由4 个位置随便放数字 3 最受限只能放两个位置。越大的数字能去的位置越少因为它在 n 范围内的倍数数量急剧减少。这给了我们一个非常重要的方向先处理受限的数字。我见到太多人一上来按位置 1、2、3... 顺序填填到位置 8 发现候选数字一大堆剪枝剪不干净搜索树膨胀得厉害。反过来从大数字往小数字放每个数字的分支都非常有限整棵树的宽度被压制住了。这就是典型的“最受限变量优先”思想在算法题里无处不在。2.2 为什么“从大到小”比“从小到大”快得多拿 n4 举例感受一下差距。从数字 4 开始4 只能在 {1,2,4} 三个位置里挑。如果从数字 1 开始1 能放 4 个位置分支直接多 33%。n 越大这种差距被指数放大n15 的时候差别可能是几百倍。还有一个隐藏好处每次把一个数字安排到某个位置位置集合就少一个。后面的数字再选的时候很多位置已经不可用这本身就是天然剪枝。如果你先处理自由的数字把受限数字留到最后走到搜索树深处才发现某个数字无路可走整个分支都得回溯重来这种浪费特别致命。我在本地做过对比n10 时从小到大放要跑大概 2 秒多换成从大到小放瞬间变成几十毫秒。这个顺序选择比你想的重要得多排列计数题的性能差距很大程度就取决于“谁先选”。2.3 记忆化让“重复子问题”只算一次光剪枝还不够。仔细想想 DFS 的过程假设现在还剩数字 {1,2,3} 没放剩余位置集合是固定的几个位置那么不管前面数字 4 是怎么放导致进入这个局面的后面能放出的方案数一定是一样的。用一个具体的例子说n4 时4 放在位置 1 后进入状态 A再走几步可能碰到“剩余数字 1、2剩余位置 2、3”的局面4 放在位置 2 后进入状态 B走几步也可能碰到完全相同的“剩余数字 1、2剩余位置 2、3”。如果不记忆化这个局面会被重复计算两遍。数字一多重复计算的次数是爆炸性的。怎么描述一个局面两个信息就够了当前正在放哪个数字以及哪些位置已经被占用。因为我们的递归顺序固定是从大到小所以“当前数字是 x”等价于“x 及 x 以下的数字都还没放”一个整数指针就能代表剩余数字集合不需要额外的集合编码。位置占用信息用二进制位掩码最合适这就是状态压缩。3. 状态压缩 记忆化 DFS从思路到可运行代码3.1 状态编码位运算其实没那么难用一个 int 变量 used 表示位置占用情况第 i 位为 1 表示位置 i1 已经被占用。比如 used 的二进制是 0101低三位分别是 1、0、1就表示位置 1 和位置 3 已占用位置 2 空闲。检查位置 pos 是否可用用(used (1 (pos - 1))) 0占用它用used | (1 (pos - 1))。这两行是状态压缩题的通用操作背下来都不为过。注意 pos 从 1 开始所以位移要减 1这点很容易写错。完整状态用 (num, used) 二元组表示。为了放进 HashMap 做记忆化我习惯把两个 int 拼成一个 long 作为 keylong key ((long) num 32) | (used 0xffffffffL);n 不超过 20 时used 只用得到低 20 位拼 key 不会有歧义。如果你能确定 n 更小比如 ≤ 15用(num 15) | used这类紧凑编码也完全没问题key 更小、哈希更快。我建议写成移位 32 位的通用版本省得每次都要根据 n 重新算编码。3.2 完整代码Javaimport java.util.ArrayList; import java.util.HashMap; import java.util.List; import java.util.Map; import java.util.Scanner; public class Main { private static int n; // 每个数字的可放位置列表 private static ListInteger[] candidates; // 记忆化缓存状态 (num, used) - 方案数 private static MapLong, Long memo new HashMap(); public static void main(String[] args) { Scanner sc new Scanner(System.in); n sc.nextInt(); sc.close(); // 预处理候选位置表 candidates new ArrayList[n 1]; for (int num 1; num n; num) { candidates[num] new ArrayList(); for (int pos 1; pos n; pos) { if (num % pos 0 || pos % num 0) { candidates[num].add(pos); } } } System.out.println(dfs(n, 0)); } // 当前需要放置数字 num已占用位置掩码为 used private static long dfs(int num, int used) { if (num 0) { return 1; // 所有数字都放完这是一条合法路径 } long key ((long) num 32) | used; Long cached memo.get(key); if (cached ! null) { return cached; } long count 0; for (int pos : candidates[num]) { int bit 1 (pos - 1); if ((used bit) ! 0) { continue; // 这个位置已经被占 } count dfs(num - 1, used | bit); } memo.put(key, count); return count; } }几个设计点值得说。第一候选位置列表预处理把“能不能放”的判断提前算好DFS 里不再每次做取模。取模本身不贵但在调用次数上百万次时能省就省。第二递归边界是 num0表示所有数字处理完毕返回 1。第三返回类型用 long因为 n 到 15 左右方案数就可能超过 int 上限提前避坑。3.3 复杂度分析到底快在哪理论上状态数不超过 n 乘以 2 的 n 次方每个状态内遍历当前数字的候选位置。候选位置数量大约是“num 的约数个数加上 num 的倍数个数”平均远小于 n。所以理论复杂度大概是 O(n × 2^n × d)其中 d 是候选位置的平均个数。但实际搜索量远小于这个上界原因有三个从大到小的剪枝让很多状态根本到不了某个数字一旦没有可用位置分支立即终止记忆化让相同局面只算一次。实测下来 n15 在毫秒级n20 也能在秒级完成。和纯暴力 n12 就跑不动相比这个方案完全够用。3.4 参数选择的两点心得第一别把 n 想成 30 以上。2 的 30 次方的状态规模任何记忆化搜索都扛不住。这题机考数据范围就是冲着状态压缩可行设计的如果你某天遇到 n 上 30 的类似题说明要用数学方法而不是搜索常见套路是找规律或者线性递推那是另一个级别的题。第二HashMap 的 key 编码要尽量减少碰撞。我用(num 32) | usednum 占高 32 位used 占低 32 位只要数字不超过 31 位范围编码就是一一映射不会把两个不同状态映射成同一个 key。千万别图省事用字符串当 key比如num # usedn12 的时候 HashMap 里全是字符串对象内存和时间都会炸。4. 边界条件、常见坑与调试实录4.1 边界值逐个测我拿到一套新代码习惯先跑冒烟测试这题我测的结果如下n输出说明11唯一排列 [1]1%10合法22[1,2] 和 [2,1] 都合法33[1,2,3]、[2,1,3]、[3,2,1]48手工枚举 24 个排列后验证一致这组小数据就是最好的回归测试用例。以后改代码随手跑一遍 n1 到 n4能挡住绝大多数玄学 bug。特别注意 n1很多人把位移写成1 pos遇到 n1 时 pos1 位移到 2越界访问直接炸。4.2 常见问题速查表症状原因处理结果比预期大记忆化 key 冲突两个不同状态撞到同一个 key检查 key 编码确保 num 和 used 的位段不重叠n1 或 n2 时越界位移写错或者候选列表索引从 0 开始统一用 pos 从 1 到 nbit 1 (pos-1)结果明显偏小整除条件写成“与”而不是“或”用 num%pos0 || pos%num0n18 以上超时没做记忆化或每次 DFS 内重新算候选预处理候选表加上 HashMap 缓存输出一直是 0递归顺序反了从小往大放导致死路太多改成从 n 往 1 放4.3 两个我实际踩过的坑第一个坑就是递归顺序。我不止一次在类似题里默认“按顺序填”结果一到 n10 就超时。后来发现问题不在记忆化而在处理顺序。前面说过从大到小放和从小到大放性能差距能有几十倍。这个坑光看代码很难发现必须对比测试才看得见。第二个坑是记忆化 key 的构造。我一开始图省事用了字符串拼接n12 时 HashMap 的内存直接爆掉。换成 long key 之后时间和内存开销都降了两个量级。算法题里能用基本类型就别用对象类型这条经验在状态压缩题上特别灵验。还有一个小细节递归深度等于 nJava 默认栈深几千层n20 完全安全。但如果哪天题目改成 n 上万还递归就会栈溢出那时候得改成循环或者找数学规律。5. 延伸思考这个套路能迁移到哪里5.1 条件变一变思路还成立吗如果题目改成“p[i] 和 i 互质”候选位置表从“约数加倍数”变成“所有与 num 互质的数”。核心框架不用动只需要改预处理那一段把整除判断换成最大公约数判断。如果改成“p[i] i 为质数”同样只是候选表变化DFS 结构完全复用。这就是我为什么强调要把候选位置预处理单独拎出来它把“判定逻辑”和“计数框架”解耦了。题目再怎么换条件你改的只是候选表的构造方式搜索和记忆化部分原封不动。5.2 类似的“排列计数”题型模板我自己的做题模板是这么拆的。第一步先判断输出要求的是方案数还是构造一组解第二步如果是计数且 n 在 20 以内直接考虑状态压缩加记忆化 DFS第三步如果 n 到 30 以上考虑矩阵快速幂、容斥或者找规律这类题一般有更强的数学背景第四步无论哪种情况都先预处理“决策集合”让 DFS 内部的分支判断尽量变成 O(1) 的位运算。这套模板从八皇后到旅行商问题再到各种排列计数题都能用。状态压缩的核心永远就一句话用整数编码集合用集合当状态做记忆化。理解了这句话你看到“n ≤ 20”的计数题就会有条件反射。5.3 最后再聊一个优化技巧其实还有一个优化我没写进主代码如果预处理时发现某个数字的候选位置里在当前已用掩码下只剩一个空位可以直接确定放置位置少展开一层递归。这个优化叫“单值剪枝”实现起来就是在遍历候选位置时统计空闲位置的数量等于 1 时直接放。我试过在 n16 附近能让耗时再降三成左右。不过代码会稍微绕一点性价比取决于你面对的数据范围。我建议先把基础版跑通确认结果正确再考虑要不要加这层优化。过早优化是算法题里最常见的毛病先把逻辑写对再谈性能。我个人在实际做题中的体会是像 HJ143 这种排列计数题真正的门槛不是 DFS 本身而是能不能想到“把状态压缩进一个整数、把重复子问题缓存起来”。我第一次做这题也想用排列组合公式硬推折腾了半天发现 n 到 8 以上闭式解就非常难看最后还是老老实实回到状态压缩加记忆化代码十分钟写完一次提交通过。如果你也卡在这一题建议把上面的 Java 代码照抄跑一遍再改造成你自己的版本跑通 n1 到 n10你就能彻底吃透这套排列计数的通用打法。