1259. Handshakes That Don't Cross

[altay9]

Varsayılan kod:

class Solution {
    public int numberOfWays(int num_people) {
        
    }
}

[altay9]

This question can be interpreted as a DP question as well as a Catalan Numbers question.

https://www.youtube.com/watch?v=0pTN0qzpt-Y&ab_channel=KeertiPurswaniKeertiPurswani

[ErdemT09]

Each handshake divides the people into two different groups. The number of handshakes in these groups would yield us the number of handshakes in the divison. If we take, for example, the node 1 as the pivot, there would be n/2 of such divisions.
The recursive formula should look something like this:

handshakes(n) := hs(n)
hs(0) := 1
hs(2) := 1
hs(n) := sum( hs(2*a)*hs(n-2*(a+1)), 0≤a≤(n/2-1) ) 
= hs(0)*hs(n-2) + hs(2)*hs(n-4) + hs(4)*hs(n-6) ... + hs(n-2)*hs(0)

From this, we can check:
hs(4) = hs(0)*hs(2)+hs(2)*hs(0) = 2 (true)
hs(6) = hs(0)*hs(4)+hs(2)*hs(2)+hs(4)*hs(0) = 5 (true)
where hs(n) ≡ Catalan(n/2)