Leetcode Problem 634. Find the Derangement of An Array

634. Find the Derangement of An Array

Leetcode Solutions

Dynamic Programming Approach

  1. Initialize a table dp of size n + 1 to store the number of derangements for each number from 0 to n.
  2. Set the base cases: dp[0] = 1 and dp[1] = 0.
  3. 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]).
  4. Since the answer can be very large, take each dp[i] modulo 1000000007 to prevent integer overflow.
  5. Return dp[n] as the final answer.
UML Thumbnail

Recursive Approach with Memoization

Ask Question

Programming Language
image/screenshot of info(optional)
Full Screen
Loading...

Suggested Answer

Answer
Full Screen
Copy Answer Code
Loading...