NeetCode #665LC-1259Hard1-D Dynamic ProgrammingNC Algo100
← Back to All Problems#665 · #1259 · Handshakes That Don't Cross(不相交的握手)
📌 Problem Statement & Constraints
numPeople people stand in a circle and each shakes exactly one other person's hand, with no two handshakes crossing. Return the number of ways to do this, modulo 10^9 + 7. Constraints: 1 <= numPeople <= 1000, and numPeople is even.💡 Core Algorithmic Approaches
- Fix person 0; their partner must be at an odd offset so that the two arcs formed have even lengths.
- If person 0 partners with person
k, the circle splits into two independent arcs ofk - 1andnumPeople - k - 1people, whose handshakes cannot interact. - So
dp[n] = sum(dp[k - 1] * dp[n - k - 1])over oddkfrom 1 ton - 1, withdp[0] = 1. - These are the Catalan numbers; the modulo keeps the values bounded.
💻 Benchmark Python3 Implementation
class Solution:
def numberOfWays(self, numPeople: int) -> int:
MOD = 10**9 + 7
n = numPeople
dp = [0] * (n + 1)
dp[0] = 1
for i in range(2, n + 1, 2): # only even numbers of people are valid
total = 0
for k in range(1, i, 2): # partner of person 0 splits the arc evenly
total += dp[k - 1] * dp[i - k - 1]
dp[i] = total % MOD
return dp[n]⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n^2): the nested loops over even sizes and split points.
💾 Space Complexity
O(n): the DP array.
⚠️ Interview Pitfalls & Follow-ups
- Partnering person 0 with an even-offset person: the partner must be at an odd offset so both arcs contain an even number of people.
- Forgetting the modulo: the counts grow like Catalan numbers and overflow fixed-width integers.
- Treating the arrangement as a line: fixing person 0 and splitting the circle is what makes the recursion valid.
- Iterating
iover every value: oddiare meaningless because a perfect matching needs an even count.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.