## 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 = 2Output:1

**Example 2:**

Input:num_people = 4Output:2Explanation: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 = 6Output:5

**Example 4:**

Input:num_people = 8Output:14

**Constraints:**

`2 <= num_people <= 1000`

`num_people % 2 == 0`

## Rust Solution

```
struct Solution;
use std::collections::HashMap;
const MOD: i64 = 1_000_000_007;
impl Solution {
fn number_of_ways(num_people: i32) -> i32 {
let mut memo: HashMap<i32, i64> = HashMap::new();
memo.insert(2, 2);
memo.insert(1, 1);
memo.insert(0, 1);
Self::dp(num_people / 2, &mut memo) as i32
}
fn dp(n: i32, memo: &mut HashMap<i32, i64>) -> i64 {
if let Some(&res) = memo.get(&n) {
return res;
}
let mut res = 0;
for i in 0..n {
res += Self::dp(i, memo) * Self::dp(n - 1 - i, memo);
res %= MOD;
}
memo.insert(n, res);
res
}
}
#[test]
fn test() {
let num_people = 6;
let res = 5;
assert_eq!(Solution::number_of_ways(num_people), res);
let num_people = 140;
let res = 685542858;
assert_eq!(Solution::number_of_ways(num_people), res);
}
```

Having problems with this solution? Click here to submit an issue on github.