Watch 10 video solutions for Handshakes That Don't Cross, a hard level problem involving Math, Dynamic Programming. This walkthrough by Greg Hogg has 443,129 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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 <= 1000numPeople is even.