# 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: