# 1259. Handshakes That Don't Cross

You are given an even number of people num_people that stand around a circle and each person shakes hands with someone else, so that there are num_people / 2 handshakes total.

Return the number of ways these handshakes could occur such that none of the handshakes cross.

Since this number could be very big, return the answer mod 10^9 + 7

Example 1:

Input: num_people = 2
Output: 1

Example 2:

Input: num_people = 4
Output: 2
Explanation: There are two ways to do it, the first way is [(1,2),(3,4)] and the second one is [(2,3),(4,1)].

Example 3:

Input: num_people = 6
Output: 5

Example 4:

Input: num_people = 8
Output: 14

# Solution

Approach 1: DP in O(N^2). Idea is similar to Unique Binary Search Trees.

# Code (Python)

Approach 1:

    def numberOfWays(self, num_people: int) -> int:
        # idea: DP
        ways = {0: 1, 2: 1}
        for num in range(4, num_people + 1, 2):
            ways[num] = 0
            for other_person in range(2, num + 1, 2):
                ways[num] += ways[other_person - 2] * ways[num - other_person]
        return ways[num_people] % (10 ** 9 + 7)

Approach 2:

# Code (C++)

Approach 1:

Approach 2: