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

 

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.