Readme

1259.Handshakes-That-Don't-Cross

设计dp[i]表示i个人互相握手有多少种符合题意的方法。

我们考虑最后一个人（第i个人）的握手方案。注意i必须是偶数，否则整体就无解。第i个人的选择可以是他左手第1个、第3个、第5个...直至右手第1个。考虑到第i个人的配成功，会将整个圈划分成了独立的左右两部分，因此上面这些方案其实对应了将这个圈细分的每种可能：(0,i-2),(2,i-4),(4,i-6)...(i-2,0)，其中每个括号内表示左右两部分的人数。

因此我们可以得到递推关系式：dp[i] = sum(dp[j]+dp[i-2-j])， j=0,2,...i-2