The hint video is poorly explained which makes no sense to me in any way. I really loved the hint video of count binary strings.
The guy with Apaar’s Notebook cannot explain a single problem, even the Tiling Problem was poorly explained. Can you please explain me the hint given in the video?
Thank you.
Hey @artendhiim1337 Let me explain the approach for you.
So we will try to solve this problem using dynamic programming(bottom-up approach).
Now for the person with index i, he has 2 choices ,either he can remain single and simply add up to already existing combinations up until index i-1 ,i.e, dp[i-1] or he can shake hands with some person and remaining i-2 persons can be arranged according to dp[i-2] ways. Now the person who i will pair up with can be chosen in i-1 ways.
So our loop would look something like this :-
dp[i]=dp[i-1]+(i-1)*dp[i-2];
We need to initialise dp[1]=1,dp[2]=2.
If you still have any further queries please feel free to ask,otherwise kindly mark the doubt as resolved
when we pair up with a person, we can pair up with any of the i-1 people. Why are we multiplying this number with dp[i-2]?
We are doing this because when we pick a person, the remaining i-2 persons can be arranged in dp[i-2] ways without the loss of generality, and so we are multiplying dp[i-2] every time we choose a person for i. We do this selction i-1 times ,hence we multiplied this term. Just basic combinatorics. Hope this clears your doubt.