Sat. Oct 1st, 2022

All android in one place

# 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(2N)). 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): NC1.
• Hence, total possibilities: 1 x NC1 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) + NC1 x f(N – 2)

### Recurrence Relation

f(N) = f(N-1) + NC1f(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;
}
```

## 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 the space complexity of this approach is O(N). That’s it for now, thanks for reading.

To learn more about C++ programming, data structures and algorithms, you can go through the following articles.

https://www.journaldev.com/55710/tower-of-hanoi-in-c-solved

www.hello-android.com

#### You may have missed 1 min read

#### [Video] Meet the Youth Changing the World Through Samsung’s Solve for Tomorrow Program – Samsung Global Newsroom 6 min read

#### How Samsung Elevates the UX Design of Z Flip4 and Z Fold4 – Samsung Global Newsroom 2 min read

#### Samsung’s Galaxy Experience Set To Return This October With a New San Francisco Space – Samsung Global Newsroom 6 min read