Sat. Oct 1st, 2022

Hello Android

All android in one place

Friends Pairing Problem Using Dynamic Programming In C++

2 min read

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;
}
Friends Pairing Problem Code

Output

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

Further Readings

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

https://www.journaldev.com/61310/sort-linked-lists-cpp

www.hello-android.com

Leave a Reply

Your email address will not be published. Required fields are marked *

Hello android © All rights reserved. | Newsphere by AF themes.