Count Derangements (Permutation such that no element appears in its original position)

A Derangement is a permutation of n elements, such that no element appears in its original position. For example, a derangement of {0, 1, 2, 3} is {2, 3, 1, 0}.
Given a number n, find total number of Derangements of a set of n elements.

Examples :

Input: n = 2
Output: 1
For two elements say {0, 1}, there is only one
possible derangement {1, 0}

Input: n = 3
Output: 2
For three elements say {0, 1, 2}, there are two
possible derangements {2, 0, 1} and {1, 2, 0}

Input: n = 4
Output: 9
For four elements say {0, 1, 2, 3}, there are 9
possible derangements {1, 0, 3, 2} {1, 2, 3, 0}
{1, 3, 0, 2}, {2, 3, 0, 1}, {2, 0, 3, 1}, {2, 3,
1, 0}, {3, 0, 1, 2}, {3, 2, 0, 1} and {3, 2, 1, 0}

So the java code for the above program is:

import java.util.Arrays;

public class Main {

    static int countDer(int n)
    {
        // Base cases
        if (n == 1) return 0;
        if (n == 2) return 1;

        // countDer(n) = (n-1)[countDer(n-1) + der(n-2)]

        return (n - 1) * (countDer(n - 1) + countDer(n - 2));
    }
    
    public static void main (String[] args)
    {
        int n = 4;
        System.out.println( "Count of Derangements is "
                +countDer(n));

    }
}

Time Complexity : O(2^n)

Dynamic programming approach

import java.util.Arrays;

public class Main {

    static int countDer(int n,int[] dp)
    {
        // Base cases
        if (n == 1) return 0;
        if (n == 2) return 1;

        // countDer(n) = (n-1)[countDer(n-1) + der(n-2)]
        if(dp[n] != -1)
            return dp[n];

        dp[n] = (n - 1) * (countDer(n - 1,dp) + countDer(n - 2,dp));
        return dp[n];
    }
    
    public static void main (String[] args)
    {
        int n = 5;
        int[] dp = new int[n+1];
        Arrays.fill(dp,-1);
        System.out.println( "Count of Derangements is " +countDer(n,dp));

    }
}

Time Complexity : O(n)

Space Complexity : O(n)