JAVA and DP Solution with detailed explanation.


  • 0
    N
    public int findDerangement(int n) {
        if (n == 1) {
            return 0;
        }
        long res = 1;
        long lastRes = 0;
        long lastLast = 0;
        for (int i = 3; i <= n; i++) {
            lastLast = lastRes;
            lastRes = res;            
            res = (lastLast + lastRes % 1000000007) * (i - 1) % 1000000007;
        }
        return (int)(res % 1000000007);
    }

  • 0
    N

    Explanation:
    1, say we have n == 7, the number 1 can replace any of the 2 to 7, and each of that replacement is identical, so after we calculate the result, just multiply by 6.
    2, now say we use 1 to replace 4, then for the number 4 alone, we have two options, either put 4 back to its position in 2, 3, 4, 5, 6, 7 which should the result of 6 numbers -> last result, or simply be disappeared, then we are left with 5 numbers 2, 3, 5, 6, 7 -> lastLast result. Then just add the two results together and multiply by 6, you will get the correct number
    3, why DP? last is the result we calculated for k - 1 numbers, and lastLast is the result we calculated for k - 2 numbers


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.