题目描述： 在组合数学中，如果一个排列中所有元素都不在原先的位置上，那么这个排列就被称为错位排列。 给定一个从 1 到 n 升序排列的数组，你可以计算出总共有多少个不同的错位排列吗？ 由于答案可能非常大，你只需要将答案对 109+7 取余输出即可。
样例 1: 输入: 3 输出: 2 解释: 原始的数组为 [1,2,3]。两个错位排列的数组为 [2,3,1] 和 [3,1,2]。
注释: n 的范围是 [1, 106]。
方法1： 主要思路： （1）动态规划； （2）定义动态转移方程，在增加第 i 个数时，组成的错位排列可以从之前的状态推导出来，第 i 个数可以找出 （i-1）个位置放置，对应的放的位置，比如是j，则 j 可分两种情形，一种是放置到 i 的位置，则剩余的（i-2）个数组成错位排列，j 不能放到第 i 个位置，则相当于是一个 （i-1）个数的错位排列，故dp[i]=(i-1)*(dp[i-1]+dp[i-2]); （3）根据题意，增加求余操作即可；
class Solution { public: int findDerangement(int n) { if(n==1){ return 0; } if(n==2){ return 1; } vector<int> dp(n+1,0); dp[2]=1; for(long i=3;i<=n;++i){ dp[i]=(int)((i-1)*(dp[i-1]+dp[i-2])%1000000007); } return dp[n]; } };方法2： 主要思路： （1）每个位置的错位排列的数量只和前两个位置的相关，故可以减少内存的使用，只是用两个辅助变量即可；
class Solution { public: int findDerangement(int n) { if(n==1){ return 0; } if(n==2){ return 1; } int pre=0; int cur=1; for(long i=3;i<=n;++i){ int tmp=(int)((i-1)*(pre+cur)%1000000007); pre=cur; cur=tmp; } return cur; } };