---

0634. 寻找数组的错位排列

• 标签：数学、动态规划、组合数学
• 难度：中等

题目链接

• 0634. 寻找数组的错位排列 - 力扣

题目大意

描述：

在组合数学中，如果一个排列中所有元素都不在原先的位置上，那么这个排列就被称为 错位排列。

给定一个从 $1$ 到 $n$ 升序排列的数组。

要求：

返回 不同的错位排列 的数量。

由于答案可能非常大，你只需要将答案对 $10^9 + 7$ 取余输出即可。

说明：

• $1 \le n \le 10^6$。

示例：

• 示例 1：

输入：n = 3
输出：2
解释：原始的数组为 [1,2,3]。两个错位排列的数组为 [2,3,1] 和 [3,1,2]。

• 示例 2：

输入：n = 2
输出：1

解题思路

思路 1：动态规划

思路 1：算法描述

错位排列（Derangement）是组合数学中的经典问题。设 $D(n)$ 表示 $n$ 个元素的错位排列数量。

递推公式：

$$D(n) = (n-1) \times [D(n-1) + D(n-2)]$$

推导思路：

• 考虑第 $n$ 个元素，它不能放在第 $n$ 个位置。
• 假设第 $n$ 个元素放在第 $k$ 个位置（$1 \le k \le n-1$）。
• 情况 1：第 $k$ 个元素放在第 $n$ 个位置，剩余 $n-2$ 个元素错位排列，方案数为 $D(n-2)$。
• 情况 2：第 $k$ 个元素不放在第 $n$ 个位置，相当于 $n-1$ 个元素的错位排列，方案数为 $D(n-1)$。
• 第 $n$ 个元素有 $n-1$ 种选择，所以 $D(n) = (n-1) \times [D(n-1) + D(n-2)]$。

初始条件：

• $D(0) = 1$（空排列）
• $D(1) = 0$（1 个元素无法错位）
• $D(2) = 1$（只有 $[2, 1]$ 一种）

思路 1：代码

class Solution:
    def findDerangement(self, n: int) -> int:
        MOD = 10**9 + 7
        
        # 特殊情况
        if n == 1:
            return 0
        if n == 2:
            return 1
        
        # 动态规划
        dp_prev2 = 1  # D(0)
        dp_prev1 = 0  # D(1)
        
        for i in range(2, n + 1):
            dp_curr = ((i - 1) * (dp_prev1 + dp_prev2)) % MOD
            dp_prev2 = dp_prev1
            dp_prev1 = dp_curr
        
        return dp_prev1

思路 1：复杂度分析

• 时间复杂度：$O(n)$，需要计算从 $2$ 到 $n$ 的所有错位排列数。
• 空间复杂度：$O(1)$，只使用了常数额外空间。