LeetCode 634. 寻找数组的错位排列Find the Derangement of An Array难度中等标签数学、动态规划、组合数学一、题目原文给定一个整数n原始数组是[1,2,3,…,n]。错位排列derangement是一种排列要求没有任何元素出现在它原来的位置上。求该数组一共有多少种错位排列方案。因为答案可能很大请返回结果对109710^971097取模。示例输入 n 3输出 2原始数组 [1,2,3]合法错位排列[2,3,1]、[3,1,2]一共2种输入 n 1输出 0数组 [1]只能放在原位没有错位方案输入 n 2输出 1原始 [1,2]唯一错位[2,1]约束1≤n≤1061 \le n \le 10^61≤n≤106二、费曼学习法拆解思路用大白话讲懂像讲给小白费曼核心不要直接甩公式先举例子分类讨论再推递推式再优化空间1. 定义 D(n)D(n)D(n)D(n) n个数的错位排列总数。基础边界先看小例子找感觉D(1) 0只有数字1只能站原位没法错位D(2) 1交换1、2仅此1种D(3) 2D(4) 92. 推导递推公式核心逻辑我们现在处理数字n它不能放在第n个位置所以它可以放在前面 n-1 任意一个位置位置1位置2 … 位置n-1一共n-1种选择。假设我们把数字n放到位置i。现在分两种情况讨论数字i放哪里情况①数字i放到位置nn和i互相交换交换完这两个数已经处理完毕。剩下还有 n-2 个数需要错位排列方案数 D(n-2)情况②数字i不能放到位置n现在数字i不能放位置n其他数字也不能放自己原来位置。等价剩下 n-1 个数做错位排列方案数 D(n-1)✅ 两种情况相加并且前面有n-1种位置选择D(n)(n−1)×[D(n−1)D(n−2)]\boldsymbol{D(n) (n-1) \times [D(n-1)D(n-2)]}D(n)(n−1)×[D(n−1)D(n−2)]取模MOD1097MOD10^97MOD1097一句话记忆第n个数字有n-1个坑可以放放完之后要么两数互换剩D(n-2)要么i被限制不能放n变成D(n-1)。3. 解法分类递归暴力不可行会大量重复计算n大直接栈溢出时间爆炸DP数组保存D(1),D(2)…D(n)时间O(n)空间O(n)空间优化DP推荐只保留前两项 D(n-1), D(n-2)时间O(n)空间O(1)适配n到1e6上限三、Python代码实现 逐行详细注释解法1空间优化DP最优O(n)时间O(1)空间推荐deffindDerangement(n:int)-int:# 定义取模常量题目要求结果对10^97取模MOD10**97# 边界条件ifn1:# 只有1个元素无法错位直接返回0return0ifn2:# [1,2]只能交换1种方案return1# prev2 代表 D(n-2)初始D(1)0prev20# prev1 代表 D(n-1)初始D(2)1prev11# 从i3一直循环计算到inforiinrange(3,n1):# D(i) (i-1) * (D(i-1)D(i-2)) mod MODcurrent((i-1)*(prev1prev2))%MOD# 更新两个前置变量准备下一轮循环# 原来的D(n-1)变成下一轮D(n-2)prev2prev1# 当前计算得到D(i)作为下一轮D(n-1)prev1current# 循环结束prev1就是D(n)returnprev1# 测试示例if__name____main__:print(findDerangement(1))# 0print(findDerangement(2))# 1print(findDerangement(3))# 2print(findDerangement(4))# 9print(findDerangement(5))# 44解法2DP数组版本方便看完整序列O(n)空间deffindDerangement_dp_array(n:int)-int:MOD10**97ifn1:return0# dp数组 dp[k] 代表k个数字的错位排列数量dp[0]*(n1)dp[1]0# D(1)0dp[2]1# D(2)1# 从3遍历到nforiinrange(3,n1):dp[i]((i-1)*(dp[i-1]dp[i-2]))%MODreturndp[n]# 测试print(findDerangement_dp_array(4))# 9解法3递归仅教学不适合大数据会超时deffindDerangement_recursive(n:int)-int:MOD10**97# 边界ifn1:return0ifn2:return1# 递推公式直接写递归return((n-1)*(findDerangement_recursive(n-1)findDerangement_recursive(n-2)))%MOD# n超过20就明显变慢n1e6直接崩溃print(findDerangement_recursive(4))#9四、应用场景举例错位排列真实使用场景场景1密码/信封问题经典错位排列原型有n封信n个信封每封信必须装错信封求总共有多少种装法。就是本题D(n)就是全部装错的方案数。场景2抽奖所有人不能抽到自己的礼物交换礼物聚会n个人每人准备一份礼物随机抽签任何人不能抽到自己准备的礼物求总共有多少种抽法。 直接调用findDerangement(n)。场景3测试用例生成、排列组合概率计算求随机排列中没有一个元素落在原位的概率PD(n)/n!P D(n)/n!PD(n)/n!当n很大时概率趋近1/e≈0.36791/e ≈ 0.36791/e≈0.3679自然常数倒数错位排列经典结论。比如n100个人随机抽礼物大约36.79%概率所有人都没有拿到自己的礼物。场景4哈希/置换密码、置换打乱算法密码学里构造置换要求置换中不存在不动点没有元素映射到自身需要统计这种置换总数使用错位排列。五、费曼复盘检验你懂没懂自问自答QD(n)公式怎么来的A数字n有n-1个位置放分两种情况n和i互换剩下n-2个i不能放到n剩下n-1个错位。相加 ×(n-1)。Q为什么要不断取模AD(n)数值爆炸增长n1e6时数字极大Python虽然支持大整数但题目强制要求返回mod 1e97中途取模防止数字过大拖慢运算。Q为什么递归不行A递归重复计算D(n-1),D(n-2)指数级时间n稍微大一点栈溢出。迭代DP只向前保存两个变量线性时间。Qn很大1e6空间优化版本为什么能跑A只存prev1、prev2两个变量常数空间循环1e6次Python可以快速跑完。推错位排列另一个公式D(n)n!⋅(1−11!12!−13!...(−1)n1n!)D(n)n!\cdot(1-\frac1{1!}\frac1{2!}-\frac1{3!}...(-1)^n\frac1{n!})D(n)n!⋅(1−1!1​2!1​−3!1​...(−1)nn!1​)并写代码实现。