1259. Handshakes That Don't Cross

Use dynamic programming.

Let dp[n] be the number of ways that n people can handshake.

Then fix a person as a pivot and turn for every other person who will have a handshake, the answer is the sum of the products of the new two subproblems.