If you don't understand


  • 0
    P

    This is actually a simple DP problem.
    DP formula is: D(n) = (n-1) [D(n-2) + D(n-1)]

    I don't understand this at start so I read other discuss, didn't found their explanation very clear, so I'd like to do a more detailed explanation here.

    let's consider what D(n) means, it means the number of derangement for an array with index from 1 to n, and value from 1 to n.
    Then let's think about value n, we know it can not be put on index n, instead, it can be put on index 1 to n-1, so there are n-1 possibilities.
    For each of the situation above, let's say value n is put on index i, then we need to discuss about where we put value i:
    1.if value i is put on index n (looks like value i and value n swapped their positions), then we can just ignore value i, value n, index i, index n, what's left are n-2 different values and n-2 different indexes, the problem becomes D(n-2).
    2.if value i is not put on index n, then we can only ignore value n and index i, what's left are n-1 different values and n-1 different indexes, each value has an index that it can not be put on. (value i can not be put on index n here) So the problem becomes D(n-1).

    Therefore, D(n) = (n-1) [D(n-2) + D(n-1)].

    Simple DP solution:

    class Solution {
        public int findDerangement(int n) {
            if (n <= 1) return 0;
            long dp[] = new long[n + 1];
            long mod = 1000000007;
            dp[2] = 1;
            for (int i = 3; i <= n; i++) {
                dp[i] = (i - 1) * (dp[i - 1] + dp[i - 2]) % mod;
            }
            return (int)dp[n];        
        }
    }
    

    Optimize space to O(1):

    class Solution {
        public int findDerangement(int n) {
            if (n <= 1) return 0;
            if (n == 2) return 1;
            long prevPrev = 0, prev = 1, curr = 0;
            long mod = 1000000007;
            for (int i = 3; i <= n; i++) {
                curr = (i - 1) * (prevPrev + prev) % mod;
                prevPrev = prev;
                prev = curr;
            }
            return (int)curr;
        }    
    }
    

Log in to reply
 

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