# Handshakes That Dont Cross

#### Created: April 2, 2020 by [lek-tin]

##### Last updated: April 2, 2020

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
```

#### Constraints

`2 <= num_people <= 1000`

`num_people % 2 == 0`

### Solution

```
class Solution:
def numberOfWays(self, num_people: int) -> int:
MOD, N = 10**9+7, num_people//2
dp = [0] * (N+1)
dp[0] = 1
# dp[i] represents # of ways to shake hands when the first person shakes the ith person
for i in range(1, N+1):
# if the first person shakes hands with the jth person
# this divide people into two groups: [2:j-1] and [j+1:N]
# optimal substructure: if i shakes hands with k, f(i) = f(i) + f(j-1)*f(i-1-j)
for j in range(i):
dp[i] = (dp[i] + dp[j]*dp[i-1-j]) % MOD
return dp[N]
```