题意

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 10^9 + 7.

样例

Given n = 3, return 2.

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

1.解题思路

  咋一看这个题，还真是有点懵逼，其实认真想一想，这个题是非常的简单的。
  我们假设dp数组，dp[i]求得是一共有i个数字的值；dp[i + 1],相对于dp[i]的情况，就是多了一个i + 1的数字。
  这里需要分为两种情况：
  1.前面i个数字都是符合要求的，那么当前i + 1可以跟前面的i个数字任意一个交换，所以为 i * dp[i]。
  2.前面i个数字中有一个不符合要求，也就是它的value和index相等了。这种情况下，i + 1必须跟那个不符合要求的交换，由于前面有i 个数字，每个数字都有可能不符合要求，所以是 i * dp[i - 1]。其中dp[i - 1]就是有一个数字不符合要求的情况数目。
  从而，得知，dp[i + 1] = i * (dp[i ] + dp[i - 1]);

2.代码

    public int findDerangement(int n) {

        if(n <= 3){
            return n - 1;
        }

        int dp[] = new int[n + 1];
        dp[2] = 1;
        dp[3] = 2;

        for(int i = 4; i <= n; i++){
            long t = (i - 1) * ((long)dp[i - 1] + dp[i - 2]);
            dp[i] = (int) (t % (1e9 + 7));
        }

        return dp[n];
    }