Leetcode Problem 1259. Handshakes That Don't Cross

1259. Handshakes That Don't Cross

Leetcode Solutions

Approach: Bottom-Up Dynamic Programming

  1. Initialize an array dp of length numPeople / 2 + 1 and set dp[0] = 1.
  2. Iterate i from 1 to numPeople / 2 inclusive.
    • For each i, iterate j from 0 to i - 1 inclusive.
    • Update dp[i] by adding dp[j] * dp[i - j - 1] to it, modulo 10^9 + 7.
  3. Return dp[numPeople / 2] as the final answer.
UML Thumbnail

Approach: Catalan Numbers

Ask Question

Programming Language
image/screenshot of info(optional)
Full Screen
Loading...

Suggested Answer

Answer
Full Screen
Copy Answer Code
Loading...