将1到n的自然数放到1到n的n个位置，其中元素i不放在位置i，求方案总数。
状态：dp[i]表示前i个位置错位排序的方案数
答案：dp[n]
状态转移方程：
\(dp[i] = (i - 1) * (dp[i - 1] + dp[i - 2])\)
情况1：前i-1个位置有0个位置是元素与下标相同的，将元素i与前i-1个位置的任一元素对调构成错位，贡献为 \((i - 1) * dp[i -1]\)
情况2：前i-1个位置有1个位置j是元素与下标相同的，将i和j对调，则贡献为 $(i - 1) * dp[i - 2] $
初始状态：
\(dp[1] = 0, dp[2] = 1\)
标签：元素,错位,对调,位置,排序,dp From： https://www.cnblogs.com/libohan/p/17671849.html