Friends Pairing Problem

Given n friends, each one can remain single or can be paired up with some other friend. Each friend can be paired only once. Find out the total number of ways in which friends can remain single or can be paired up.

Examples :

Input  : n = 3
Output : 4

Explanation
{1}, {2}, {3} : all single
{1}, {2, 3} : 2 and 3 paired but 1 is single.
{1, 2}, {3} : 1 and 2 are paired but 3 is single.
{1, 3}, {2} : 1 and 3 are paired but 2 is single.
Note that {1, 2} and {2, 1} are considered same.

f(n) = ways n people can remain single 
       or pair up.

For n-th person there are two choices:
1) n-th person remains single, we recur 
   for f(n - 1)
2) n-th person pairs up with any of the 
   remaining n - 1 persons. We get (n - 1) * f(n - 2)

Therefore we can recursively write f(n) as:
f(n) = f(n - 1) + (n - 1) * f(n - 2)

class Solution {
    // O(n) -> space solution
    public int countFriendsPairings(int n) {
        if (n == 0)
            return 1;
        // Recursive formula -> 2 case :
        // 1) n stays single -> fn(n-1)
        // 2) n pairs with anyone from 1->n-1 => (n-1)*fn(n-2)
        // Fn(n-2) shows the ans from remaining n-2 people
        // dp[i] -> Number of ways i people can stay paired up or single
        int dp[] = new int[n + 1];
        dp[0] = 1;
        dp[1] = 1;
        for (int i = 2; i <= n; i++) {
            dp[i] = dp[i - 1] + (i - 1) * dp[i - 2];
        }
        return dp[n];
    }

    // O(1) space solution
    public int countFriendsPairings(int n) {
        if (n == 0 || n == 1)
            return 1;
        int dp0 = 1, dp1 = 1;
        for (int i = 2; i <= n; i++) {
            int dpi = dp1 + (i - 1) * dp1;
            dp0 = dp1;
            dp1 = dpi;
        }
        return dp1;
    }
}