LeetCode Solutions
634. Find the Derangement of An Array
Time: $O(n)$ Space: $O(n)$
class Solution {
public:
int findDerangement(int n) {
dp.resize(n + 1);
return find(n);
}
private:
constexpr static int kMod = 1'000'000'007;
vector<int> dp;
int find(int i) {
if (i == 0)
return 1;
if (i == 1)
return 0;
if (dp[i])
return dp[i];
return dp[i] = (i - 1L) * (find(i - 1) + find(i - 2)) % kMod;
}
};
class Solution {
public int findDerangement(int n) {
dp = new Long[n + 1];
return (int) find(n);
}
private static final int kMod = 1_000_000_007;
private Long[] dp;
private long find(int i) {
if (i == 0)
return 1;
if (i == 1)
return 0;
if (dp[i] != null)
return dp[i];
return dp[i] = (i - 1) * (find(i - 1) + find(i - 2)) % kMod;
}
}
class Solution:
def findDerangement(self, n: int) -> int:
kMod = 1_000_000_007
@functools.lru_cache(None)
def dp(i: int) -> int:
if i == 0:
return 1
if i == 1:
return 0
return (i - 1) * (dp(i - 1) + dp(i - 2)) % kMod
return dp(n)