Friends pairing Problem -Editorial

#1

I didn’t understand the logic of editorial that why we are using dp[I]=dp[I-1]+(I-1)*dp[I-2];

#2

Hey sumit,
we define the recurrence for the corresponding problem as
F(n) = F(n-1) + (n-1)*F(n-2)
The logic for the above recurrence can be defined by the following points:

  1. The term F(n-1) comes for the case when we choose to go alone then there are n-1 people for which we need to find the solution so we assume this is calculated by recursion.
  2. The term (n-1)*F(n-2) comes because suppose we are choosing to go in a pair then for a nth person we can choose his partner in (n-1) ways (this comes by simple PNC as [n-1]C[1]) So we multiply the factor (n-1) with F(n-2) as F(n-2) denotes the result which will give the answer for the remaining people when we have chosen a pair

So the solution boils down to 3 points

  1. Calculate the answer when we dont pair i.e. F(n-1)
  2. Calculate the answer when we pair i.e F(n-2)
  3. Multiply F(n-2) term with (n-1) because there will be n-1 ways to choose the pair

Hope this helps…

2 Likes
#3

tell me why f[2]=2 and not 3 .
suppose 2 person x and y …x goes alone or y goes alone or they they go together