Find the Derangement of An Array

每一个数字都不能放在自己的原始位置，那我们可以考虑两种情况，比如1, 3，如果3不放在第三个位置而放在第1个位置，则此时1有两种方案，一种1就放在第三个位置，一种1不放在地三个位置，如果放在第三个位置，我们要求的结果规模就减少了2，如果不放，则减少了1，再因为这种选择一共可以发生n-1次，所以最后的状态转移方程就是

dp[i] = (i - 1) * (dp[i - 1] + dp[i - 2])

根据上面方程就可以写出代码了

class Solution(object):
    def findDerangement(self, n):
        """
        :type n: int
        :rtype: int
        """
        if n < 3:
            return 1 if n == 2 else 0

        dp = [0] * (n + 1)
        dp[2] = 1
        for i in xrange(3, n + 1):
            dp[i] = ((i - 1) * (dp[i - 1] + dp[i - 2])) % (10 ** 9 + 7)
        return dp[n]