Leetcode 1259: Handshakes That Don't Cross

https://leetcode.com/problems/handshakes-that-dont-cross/description/

Notes:

This problem can be solved by dp.

Why? because, as shown in the above figures, it can be easily converted to similar questions but with smaller sizes.

Let us use dp[n] to represent the total ways for n people.

The first person can shake hands with the second one, but cannot shake hands with the second one. Why?

Because if the first person connects with the third one, then the second one have to cross the "line" to shake hands with other people.

Thus, if the first person shake hands with the jth person, this essentially divide the original circle into two parts:

one is from i+1 to the j-1 people, and the other is from j+1 to the nth people.

So we need to leave even number of people in both sides.

Thus, dp[n] = dp[0]* dp[n-2] + dp[2]*dp[n-2-2] + ... + dp[j]*dp[n-j-2].

In addition, due to symmetry, we can just calculate half of the circle.

See the code below:

class Solution {
public:
    int numberOfWays(int num_people) {
        int n = num_people, mod = 1e9+7;
        vector<long> dp(n+1, 0);
        dp[0] = 1;
        for(int i=2; i<=n; i += 2) {
            for(int j=0; j<=i-j-2; j += 2) {//calculate half circle
                if(j==i-j-2) dp[i] += dp[j]*dp[i-j-2]%mod;
                else dp[i] += 2*((dp[j]%mod)*(dp[i-j-2]%mod)%mod);
                dp[i] %=mod;
            }
        }
        return dp[n];
    }
};