Friends Pairing

https://www.geeksforgeeks.org/friends-pairing-problem/

package pep.Day20;

import java.util.Arrays;
import java.util.Scanner;

public class FriendsPairing {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        System.out.println(recursion(n));

        long[] dp = new long[n + 1];
        Arrays.fill(dp, -1);
        System.out.println(recursionMemo(n, dp));
        display(dp);

        Arrays.fill(dp, -1);
        System.out.println(recursionTabulation(n, dp));
        display(dp);
    }

    private static void display(long[] dp) {
        for (long x : dp)
            System.out.print(x + "\t");
        System.out.println();
    }

    public static int recursion(long n) {
        if (n == 0)
            return 1;

        int single = 1 * recursion(n - 1);
        int pair = 0;
        if (n > 1)  // if n > 1, then only pair will exist
            pair = (n - 1) * recursion(n - 2);
        return single + pair;
    }

    public static int recursionMemo(int n, long[] dp) {
        if (n == 0)
            return dp[n] = 1;

        if (dp[n] != -1) return dp[n];
        int single = 1 * recursionMemo(n - 1, dp);
        int pair = 0;
        if (n > 1)  // if n > 1, then only pair will exist
            pair = (n - 1) * recursionMemo(n - 2, dp);
        return dp[n] = single + pair;
    }

    public static int recursionTabulation(int N, long[] dp) {

        for (int n = 0; n <= N; n++) {
            if (n == 0) {
                dp[n] = 1;
                continue;
            }

            //if (dp[n] != -1) return dp[n];

            int single = 1 * dp[n - 1];//recursionMemo(n - 1, dp);
            int pair = 0;
            if (n > 1)  // if n > 1, then only pair will exist
                pair = (n - 1) * dp[n - 2];//recursionMemo(n - 2, dp);
            dp[n] = (single + pair) % ((long) 1e9 + 7);
        }
        return dp[N];
    }
}