leetcode634--错排(我觉得我解释的挺好的,哈哈)

# 小郑之家~

In combinatorial mathematics, a derangement is a permutation of the elements of a set, such that no element appears in its original position.

There’s originally an array consisting of n integers from 1 to n in ascending order, you need to find the number of derangement it can generate.

Also, since the answer may be very large, you should return the output mod 109 + 7.

Example 1:

Input: 3 Output: 2 Explanation: The original array is [1,2,3]. The two derangements are [2,3,1] and [3,1,2].

Note: n is in the range of [1, 106].

• 1放在n号

• 1不放在n号

f(n)=(n-1)(f(n-1)+f(n-2)).

class Solution{
public:
int find(int n){
if(n<2) return 0;
vector<long long> dp(n+1, 0);   //申请n+1个位置，初始化为0.

dp[1] = 0;
dp[2] = 1;
for(int i=3;i<n+1;i++){
dp[i] = (i-1)*(dp[i-1]+dp[i-2]) % (1000000007);
}
return dp[n];

}

};