(12) DP: Friends Pairing Problem

Question Link

Difficulty: Easy

Problem Statement: Given N find a total number of ways in which it can pair up or remain single.

Approach: If N = 1 then it can only remain in single. For N = 2 it can remain single or pair up. For N = 3 and above first it will remain single hence dp[n - 1] will be called on left n-1 elements. Second it will combine with a element and now numbers remaining are n-2 so dp[n - 2] will be called and that total dp[n - 2] will be (n-1) in number and hence dp[n-2] * (n-1).

int countFriendsPairings(int n)
{
    int dp[n + 1], mod = 1e9 + 7;
    dp[0] = 0, dp[1] = 1, dp[2] = 2;
    for (int i = 3; i < n + 1; i++)
    {
        dp[i] = dp[i - 1] + (i - 1) * dp[i - 2];
        dp[i] = dp[i] % mod;
    }
    return dp[n];
}

Subscribe to the newsletter so that you never miss any post or update just like this one.

You can follow me on Hashnode for:

• Daily Data Structure and Algorithm based questions

• Getting knowledge of various development-related tools, concepts, and practices

  Twitter , GitHub , LinkedIn and Hashnode