星野爱
错位排列原理
错位排列是指排列中所有元素都不在其原始位置的排列方式。例如，原始排列为 1, 2, 3，其错位排列有：
2, 3, 1（每个数都不在原位置）3, 1, 2（同理）
因此，3 个元素的错位排列数为 2，记为D(3) = 2。
错位排列数的递推公式为： D(n) = (n-1) \times [D(n-1) + D(n-2)] 其中，初始条件为： D(0) = 0, \quad D(1) = 0
递推公式的推导
递推公式的推导基于以下思路：
固定元素的位置选择：对于第 n 个元素，它不能放在第 n 个位置，因此有 n-1 种选择。假设第 n 个元素放在了第 k 个位置。
处理元素 k 的放置：此时元素 k 需要被放置到其他位置，有两种情况：
情况 1：元素 k 被放置到第 n 个位置。此时剩下的 n-2 个元素需要进行错位排列，方案数为 D(n-2)。
情况 2：元素 k 不被放置到第 n 个位置。此时可以将第 n 个位置视为新的 “禁区”，剩下的 n-1 个元素需要进行错位排列，方案数为 D(n-1)。
因此，对于每个 k，总方案数为 D(n-1) + D(n-2)。由于 k 有 n-1种选择，递推公式为D(n) = (n-1) \times [D(n-1) + D(n-2)]。
n = int(input())
if n == 0 or n == 1:
print(0) # 当n=0或1时，错位排列数为0
elif n == 2:
print(1) # 当n=2时，错位排列数为1
else:
# 初始化前两个状态
d_prev_prev = 0 # D(1)
d_prev = 1 # D(2)
for i in range(3, n+1):
# 递推公式计算 D(i)
d_current = (i-1) * (d_prev + d_prev_prev)
# 更新状态，为下一次迭代做准备
d_prev_prev, d_prev = d_prev, d_current
print(d_prev) # 最终结果为d_prev，即D(n)
输入处理：读取整数 n。
边界条件处理：
当 n = 0或 n = 1时，直接输出 0。
当 n = 2时，直接输出 1。
递推计算：
使用两个变量
d_prev_prev和d_prev分别保存 D(n-2) 和 D(n-1) 的值。从 i = 3 开始迭代到 n，每次迭代计算当前 D(i)的值，并更新状态变量。
输出结果：循环结束后，
d_prev即为 D(n)的值。
当 n = 3 时：
初始：
d_prev_prev = 0,d_prev = 1迭代：
d_current = (3-1) * (1 + 0) = 2输出：2
当 n = 4时：
初始：
d_prev_prev = 1,d_prev = 2迭代：
d_current = (4-1) * (2 + 1) = 9输出：9
时间复杂度为 O(n)，空间复杂度为 O(1)。
动态规划的关键特征
重叠子问题 错位排列数 O(n)的计算依赖于更小的子问题 D(n-1) 和 D(n-2)，这些子问题会被重复使用。例如：
计算 D(5))需要 D(4) 和 D(3)；
计算 D(4)需要 D(3)和 D(2)。 其中 D(3) 被多次使用，符合重叠子问题的特征。
最优子结构 错位排列的递推公式 D(n) = (n-1) \times [D(n-1) + D(n-2)] 直接将原问题的解表示为子问题解的组合，满足最优子结构性质。
状态转移方程 代码中通过
d_current = (i-1) * (d_prev + d_prev_prev)实现了递推公式，这正是动态规划中的状态转移方程。
动态规划实现细节
状态定义： 用
d_prev_prev和d_prev分别保存前两个状态 D(n-2) 和D(n-1)，这属于动态规划中的 “状态压缩” 技巧（仅保存必要的历史状态，将空间复杂度优化到 O(1)）。初始化： 根据错位排列的初始条件，设置
d_prev_prev = 0（对应 (D(1))）和d_prev = 1（对应 D(2)）。迭代计算： 通过循环从 i=3到 n，逐步计算每个状态的值，并更新状态变量，最终得到 D(n)。
对比递归与动态规划
递归解法（未优化） 若直接用递归实现递推公式：
def derangement(n): if n == 0 or n == 1: return 0 elif n == 2: return 1 else: return (n-1) * (derangement(n-1) + derangement(n-2))虽然逻辑正确，但时间复杂度为指数级 O(2^n)，因为大量子问题被重复计算（例如 D(3) 会被计算多次）。
动态规划解法（优化） 原代码通过迭代和状态压缩，将时间复杂度优化到 O(n)，空间复杂度优化到 O(1)，避免了重复计算，符合动态规划的核心优势。