在组合数学中，如果一个排列中所有元素都不在原先的位置上，那么这个排列就被称为错位排列。
给定一个从 1 到 n 升序排列的数组，你可以计算出总共有多少个不同的错位排列吗？
由于答案可能非常大，你只需要将答案对 1000000007 取余输出即可。
样例 1:
输入: 3
输出: 2
解释: 原始的数组为 [1,2,3]。两个错位排列的数组为 [2,3,1] 和 [3,1,2]。
注释:
n 的范围是 [1, 1^6]。
自我解答(动态规划)
饶了些弯子，想尝试用数学的方式解答的，但分析得越来越复杂，还是没有数学天赋啊。
点开题解发现了 “动态规划” 的标签，才意识到可以用 "动态规划" 解答，于是关掉题解开始思考 最优子结构了。
我发现，这题很像 “爬楼梯” 和 《算法导论》中 “钢条问题” 的结构。
假设 f(n) 为 大小为 n 的数组错位排列方案数。
不管是数组的哪一截，只要大小为 n ，那么其方案数应该是固定的
而且 f(n) 和 f(n+1) 之前应该存在相关联系，从而构成了 最优子结构。
分析 f(n) 和 f(n+1)， 两者直接的区别是， f(n+1) 多了一个，假如把 n 个数看作是 n 个坑位:
0 1 ... n { n + 1}
[ ], [ ], ... [ ], { new }
假设如上 前 n 项是 f(n)的其中一个错位排列方案, f(n+1) 的意义在于：多了一个坑位。
那么在这个基础上，发现 new 和 前面任何一个数 交换位置都能组成一个 f(n+1) 的方案。
因此在这里，我们知道 f(n) 的 1 个方案至少能为 f(n+1) 贡献 n 个方案， 所以，f(n)个方案就能
至少 为 f(n+1) 贡献 f(n) * n 个方案。
那么 f(n+1) 和 f(n) 是否就是 f(n+1) = f(n) * n 的关系呢？ 并没有那么简单
拿 f(3) 和 f(4) 举例, f(3) 有 [2, 3, 1] 和 [3, 1, 2] 两个方案, 根据上面分析出的，我们至少能得到
2 * 3 个 f(4)的方案：
[2, 3, 4, 1], [2, 4, 3, 1], [4, 3, 1, 2]
[3, 1, 4, 2], [3, 4, 2, 1], [4, 1, 2, 3]
但实际上，不止这 6 个方案，还有：
[2, 1, 4, 3], [3, 4, 1, 2], [4, 3, 2, 1]
仔细观察，发现和 4 调换 位置的 分别是 3，2, 1，都是调换到其调换对象 的原本位置，也就是说：
我们也可以和 N = 3时 的 “非错位排列” 做位置交换, 如 [2, 1, 3], 其中的 3 是在原本位置上,
当增加一个4号坑位，我们就可以和 3 调换顺序，于是就实现了一个 f(4) 的一个 错位排列方案。
所以，在新增一个 “位置” 时，新位置(如n+1), 必须到别的位置上去, 我们也可以和一个在原本位置的人调换顺序。
但必须保证前面的排列 是有且仅有一个是在原本位置的。
对于 n 的人来说，可以在原本位置的可以是 n 个人，这意味剩下的 n - 1 个人必须是个错位排列。
所以这里可以表示为 f(n-1) * n
因此我们可以总结出 最优子结构了:
f(n+1) = f(n) n + f(n-1) n
-> f(n+1) = (f(n) + f(n-1)) * n
可以以此写出自顶向上的动态规划算法,
但可惜超时了，原因在于数值变得非常大时，仅仅是基本运算也变得十分耗时
class Solution:
def findDerangement(self, n: int) -> int:
if n == 1: return 0
if n == 2: return 1
dp1, dp2 = 0, 1
for i in range(3, n + 1):
dp1, dp2 = dp2, (dp2 + dp1) * (i - 1)
return dp2 % 1000000007
题解
题解的动态规划思路和自己想的一致，对于大数字做了优化：
每次得到一个子问题的解，都做取模运算，把数字控制在 1000000007 的规模
class Solution2:
def findDerangement(self, n: int) -> int:
if n == 1: return 0
if n == 2: return 1
dp1, dp2 = 0, 1
for i in range(3, n+1):
dp1, dp2 = dp2, ((dp2 + dp1) * (i-1)) % 1000000007
return dp2
这个操作我自己是肯定想不到了，因为不太理解这个数学运算：
我的做法是 (a + b) % p
题解是转化成了 (a % p + b) % p
可我查了一下，去模运算的分配律应该是：(a+b) % p = ( a % p + b % p ) %p
我验证写了个脚本验证了一下，的确有 (a % p + b) % p == ( a % p + b % p ) %p
import random
p = 45
for x in range(1000000):
a = int(random.random() * 100)
b = int(random.random() * 100)
res = (a + b) % p == (a % p + b) % p
if not res:
print(res)
原题链接：https://leetcode-cn.com/problems/find-the-derangement-of-an-array