# If you don't understand

• 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;
}
}
``````

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