I want to share my experience on solving this problem. For you guys who is not able to see this question any more, here is the short version of question.

Given the number of people in the room, what is the number of handshake configuration so no handshake is crossed with each other.

• number of person: 6
• answer: 5

Reference: (https://assets.leetcode.com/users/edward454/image_1573986300.png) --> from the leetcode contest

At a first glance, I do not have any idea on how solving this problem, then I start to draw all my random idea on a piece of paper --> this is what usually I do when I do not have any idea. Then I start to realize that this problem is really similar with the triangulation from leetcode problem long time ago.

The idea is let say we have 3 variables: start, end and k.

start < k < end

1. imagine we draw a straight line from start to k. this straight line can be imagines as a line which divides 2 part of the configuration. with that in mind we can build this formula:

ans = 0
if k-start is divisible by 2:
	# we just need to times the number of possibility from the left part and right part of the configuration
	 ans += self.recur(start+1, k-1) * self.recur(k+1, end)

2. Regardless the start and end if end-start is 2 then the answer is 1. Regardless the value of end and start. With that in mind we can build a dp solution for it.

class Solution(object):
    const = 10**9 + 7
    def numberOfWays(self, num_people):
        """
        :type num_people: int
        :rtype: int
        """
        return self.recur(0, num_people-1, {})%self.const
    
    def recur(self, start, end, dp):
        if (end-start+1) == 2:
            return 1
        elif end <= start:
            return 1
        
        ans = 0
        if (end-start) in dp:
            return dp[end-start]
        for k in range(start, end+1):
            if ((k-start)+ 1)%2 == 0:
                ans += (self.recur(start+1, k-1, dp) * self.recur(k+1, end, dp))
        dp[(end-start)] = ans%self.const
        return ans