不相交的握手

/*
 * Leetcode Problem 1259: Handshakes That Don't Cross
 * 
 * Problem Statement:
 * You are given an even number of people standing in a circle. Each person shakes hands with exactly one other person such that the handshakes do not cross. Determine the number of ways these handshakes can occur.
 * 
 * Approach:
 * This problem can be solved using dynamic programming with the help of Java Streams. We can use the concept of Catalan numbers which count the number of ways to correctly match parentheses, or in this case, the number of ways to arrange handshakes.
 * 
 * The recurrence relation for Catalan numbers is:
 * C(n) = sum(C(i) * C(n-1-i)) for i from 0 to n-1
 * 
 * In this problem, we are asked to find the number of ways to arrange handshakes for 2n people.
 */

import java.util.stream.IntStream;

public class HandshakesThatDontCrossStream {
    public int numberOfWays(int numPeople) {
        if (numPeople % 2 != 0) return 0;
        int n = numPeople / 2;
        long[] dp = new long[n + 1];
        dp[0] = 1;
        IntStream.rangeClosed(1, n).forEach(i -> dp[i] = IntStream.range(0, i).mapToLong(j -> dp[j] * dp[i - 1 - j]).sum());
        return (int) dp[n];
    }

    public static void main(String[] args) {
        HandshakesThatDontCrossStream solution = new HandshakesThatDontCrossStream();
        int numPeople = 6; // Example input
        System.out.println(solution.numberOfWays(numPeople)); // Output should be 5
    }
}