Friends Pairing Problem Using Dynamic Programming In C++

Today, we’ll learn to solve the friends pairing problem using dynamic programming in C++. It’s a popular dynamic programming problem on LeetCode. Dynamic programming is one of the most difficult topics of DSA. We’ll learn to solve this problem using the concept of dynamic programming. Let’s get started.

Problem Statement for Friends Pairing

N friends are going to a party. Each friend can either go in a pair or single. Find the total number of ways in which they can go to the party.

Input Format

The input will be a single integer N.

For example,

N = 3
Possible ways = 4
 
N = 4
Possible ways = 10
 
N = 7
Possible ways = 232

Approach

The recursive approach is not enough for large values of N. The time complexity of the recursive solution is exponential with the number of friends(i.e. time complexity = O(2^N)). The recursive solution is functional only up to N = 24.

How To Deal With Dynamic Programming Problems

Dynamic programming problems are recursive problems that require some extra aid. Similar to recursive solutions, the dynamic programming solutions compute all the subproblems of a problem.

Dynamic Programming = Recursion + Memoisation = Never solve the same problem twice

Recursion: Compute all the subproblems of a problem.

Memoization: Store the results of expensive computations.

Pseudocode

Below is the step-by-step process that we’ll follow to code the solution.

• There are only two ways in which a person can go to the party.
  1. Go to the party as a couple.
     • Possible ways: You and one of your friends.
       • Total ways to select 1 friend out of (N – 1): ^NC₁.
       • Hence, total possibilities: 1 x ^NC₁ x f(N – 2)
  2. Go single.
     • Total possibilities: 1 x f(N – 1)
• Hence, the total ways for all N friends to reach the party are: go_single + go_as_a_couple
  • f(N) = f(N – 1) + ^NC₁ x f(N – 2)

Recurrence Relation

f(N) = f(N-1) + ^NC₁f(N-2) f(N) = f(N-1) + (N-1)f(N-2)

Friends Pairing Problem Using Dynamic Programming In C++ Program

#include <iostream>
#include <vector>
 
using namespace std;
 
/*
Recurrence Relation : f(N) = f(N-1) + NC1*f(N-2)
                      f(N) = f(N-1) + (N-1)*f(N-2)
*/
 
// function to compute the total possibilities
int waysToGo(int n,vector <int> dp)
{
    //base case
    // if there is only one person or no person at all
    // then there's only one possible way to go to the party
    if(n==0 || n==1)
    {
        return 1;
    }
 
    //look up case: memoisation
    // check if the answer is the result of any previous
    // computation
    if(dp[n] != 0)
    {
        // if yes, then simply return the already computed answer
        // this step avoids the recomputation of previously
        // computed solution
        return dp[n];
    }
 
    // apply the recursive relation
    //recursive relation
    dp[n] = waysToGo(n-1, dp) + (n - 1) * waysToGo(n - 2, dp);
 
    return dp[n];
}
 
// driver function
int main()
{
    cout << "Enter the value of N" << endl;
    int n;
    cin>>n;
 
    // declare and initialize the vector to store intermediate states
    vector <int> dp(n + 1, 0);
 
    // display the results
    cout << "The total number of ways to go to the party is: " << waysToGo(n, dp) << endl;
 
    return 0;
}

Output

Conclusion

In this article, we learned to solve the friends pairing problem using dynamic programming in C++. We used the concept of recursion + memorization(Dynamic Programming) to solve this problem. Dynamic programming solutions are of two types. The first is the bottom-up approach and the second one is the top-down approach. In this article, we used the top-down approach to develop the algorithm. In the end, we implemented a C++ program to demonstrate the working of our solution. The time and space complexity of this approach is O(N). That’s it for now, thanks for reading.