Friends Pairing Problem Using Dynamic Programming In C++
source link: https://www.journaldev.com/62233/friends-pairing-problem-cpp
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
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.
- 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)
- Possible ways: You and one of your friends.
- Go single.
- Total possibilities: 1 x f(N – 1)
- Go to the party as a couple.
- 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; } |
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.
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK