Dear readers, we are back again with another really interesting problem. At this point, you have already solved a lot of DP-related problems so feel free to take a stab at this problem. If you face any difficulty don't worry we will solve it together.
Important Links: Problem Link, Video Link
- You are given a number n, representing the number of friends.
- Each friend can stay single or pair up with any of their friends.
- You are required to print the number of ways in which these friends can stay single or pair up.
Let's take an example to understand this. Let's say there are 3 friends, and we will represent them as 1, 2, 3. You can choose any name for them.
Now, what do you think are the different ways we can pair them up or keep them single.
We can keep all of them single. Or we can do these.
Hence there were 4 ways to arrange them. 1-2-3, 12-3, 1-23, 13-2. Thus the answer for 3 friends will be 4.
If you still didn't understand the question watch the video from [0:00 - 2:00]
I will suggest you think about the problem for a few minutes.
Now, let's try to understand first how to create these pairings and then look into calculating the count. Here you can see we just drew all the possibilities:
If you have difficulty understanding this watch the video from [2:10 - 3:05].Now, we will traverse the Euler path to get all pairings. We are back at 23, we will get two pairings 2-3, and 23-.
Now when we reach 123 we will add a single 1 to those pairings.
Now when we traverse the remaining 3. We will get just one pairing i.e 12-3.
And finally, from 2 we will have 13-2.
Clearly, we again reached our original answer of 4. And the pairings are
1-2-3 1-23 12-3 13-2If you still have some doubts watch the video from [5:09 - 8:03]
Let's say we already have the count for n-1 friends now, we have another new friend. We can either keep that friend single this will give us the same pairings as that of n-1 friends. Also, we can pair this new friend with the n-1 friends and for each of them, the answer will be the count for n-2 friends. So (n-1)* [ pairings for n-2 friends]. If you didn't understand this fact clearly, watch the video from [8:35 - 10:17]
This generates the dp relation of
dp[i] = dp[i-1] + (i-1)*dp[i-2]Clearly, we will need a 1-D array to store the values. This problem is again very similar to that of Fibonacci only that it has this new (i-1) factor. Rest everything is the same. So try to code it yourself first.
java;
true";
We are just using a single loop with n iterations and in each iteration, we are performing constant-time operations. Hence it will be O(n).
We are using a single 1-D array of size n so the complexity will be O(n) as well. Now the question is can you solve it in less than O(n) space? I will give a hint: Look at which values does dp[i] depend on. Isn't it enough to just store the last 2 values?
