Leetcode Problem 634. Find the Derangement of An Array

634. Find the Derangement of An Array

Leetcode Solutions

Initialize a table dp of size n + 1 to store the number of derangements for each number from 0 to n.
Set the base cases: dp[0] = 1 and dp[1] = 0.
Iterate from 2 to n, and for each i, calculate dp[i] using the recurrence relation: dp[i] = (i - 1) * (dp[i - 1] + dp[i - 2]).
Since the answer can be very large, take each dp[i] modulo 1000000007 to prevent integer overflow.
Return dp[n] as the final answer.

Programming Language

Purpose:

General Question

Debug My Code

image/screenshot of info(optional)

Full Screen