LC: 1259. Handshakes That Don't Cross
https://leetcode.com/problems/handshakes-that-dont-cross/
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: 1Example 2:
Example 3:
Example 4:
Constraints:
2 <= num_people <= 1000num_people % 2 == 0
1259. Handshakes That Don't Cross:
The Essence:
Wenn n Menschen um einen Tisch sitzen, gibt es k=n/2 Paare.
Wenn Person 1 und Person X Hände schütteln, muss X eine gerade Zahl sein. Andernfalls überschreiten die Handschläge.
Wenn Person 1 und X Hände schütteln, dann wird die Gruppe in zwei neuen Gruppen getrennt, die jeweils j bzw. k-j-1 Paare enthalten.
Durch Kombination erhält man, dass dabei numberOfWays(j Paare)*numberOfWays(k-j-1 Paare) gilt. Man kann dann für alle Zahlen j die Anzahl der Handschläge summieren, um die Gesamtanzahl zu bestimmen.
Details:
Für eine detaillierte Erklärung und eine Implementation durch dynamische Programmierung bitte unser PR nachsehen.
Solutions:
Default Code:
Last updated