Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- def derangement_dp(n):
- # Base cases
- if n == 1:
- return 0
- if n == 2:
- return 1
- # Create a list to store results of subproblems
- derangements = [0] * (n + 1)
- # Initialize base cases
- derangements[1] = 0
- derangements[2] = 1
- # Fill the entries in a bottom-up manner
- for i in range(3, n + 1):
- derangements[i] = (i - 1) * (derangements[i - 2] + derangements[i - 1])
- return derangements[n]
- # Test the function
- for i in range(1, 11):
- print(f"D({i}) = {derangement_dp(i)}")
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
