1259. Handshakes That Don't Cross π
Description
You are given an even number of people numPeople
that stand around a circle and each person shakes hands with someone else so that there are numPeople / 2
handshakes total.
Return the number of ways these handshakes could occur such that none of the handshakes cross.
Since the answer could be very large, return it modulo 109 + 7
.
Example 1:
Input: numPeople = 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 2:
Input: numPeople = 6 Output: 5
Constraints:
2 <= numPeople <= 1000
numPeople
is even.
Solutions
Solution 1: Memoization Search
We design a function $dfs(i)$, which represents the number of handshake schemes for $i$ people. The answer is $dfs(n)$.
The execution logic of the function $dfs(i)$ is as follows:
- If $i \lt 2$, then there is only one handshake scheme, which is not to shake hands, so return $1$.
- Otherwise, we can enumerate who the first person shakes hands with. Let the number of remaining people on the left be $l$, and the number of people on the right be $r=i-l-2$. Then we have $dfs(i)= \sum_{l=0}^{i-1} dfs(l) \times dfs(r)$.
To avoid repeated calculations, we use the method of memoization search.
The time complexity is $O(n^2)$, and the space complexity is $O(n)$. Where $n$ is the size of $numPeople$.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
|