Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/1259.html

1259. Handshakes That Don’t Cross

Level

Hard

Description

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:

Image text

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:

Image text

Input: num_people = 6

Output: 5

Example 4:

Input: num_people = 8

Output: 14

Constraints:

  • 2 <= num_people <= 1000
  • num_people % 2 == 0

Solution

Use dynamic programming. Consider the number of pairs, which equals half the number of people. That is, let numPairs = num_people / 2. Create an array dp of length numPairs + 1, where dp[i] represents the number of ways of i pairs of people’s handshakes such that none of the handshakes cross. Initialize dp[0] = 1 and dp[1] = 1. If there are two people, which is equivalent to one pair, then obviously there is one handshake and one way. If there are no people, then there is no handshake, which is also one way.

For i from 2 to numPairs, suppose the people are labelled from 1 to 2 * numPairs, and consider the person with label 1, who can only shake hands with people with even labels to make sure none of the handshakes cross. Suppose the person with label 1 shakes hands with the person with label n, then there must be an even number of people in the label range 2 to n - 1 and there must be an even number of people in the label range n + 1 to 2 * numPairs, so n must be an even number. For each even number n, since the person with label 1 and the person with label n shake hands, the rest of the people are divided into two groups, which have n - 2 people and 2 * numPairs - n people respectively. Therefore, for each j from 0 to i - 1, update dp[i] = dp[i] + dp[j] * dp[i - j - 1]. Remember to do the mod operation on each element of dp. Finally, return dp[numPairs].

  • class Solution {
    public int numberOfWays(int num_people) {
        int numPairs = num_people / 2;
        if (numPairs == 0 || numPairs == 1)
            return 1;
        final int MODULO = 1000000007;
        long[] dp = new long[numPairs + 1];
        dp[0] = 1;
        dp[1] = 1;
        for (int i = 2; i <= numPairs; i++) {
            for (int j = 0; j < i; j++)
                dp[i] = (dp[i] + dp[j] * dp[i - j - 1]) % MODULO;
        }
        return (int) (dp[numPairs] % MODULO);
    }
}

All Problems

All Solutions