题目大意：
不相交的握手
偶数 个人站成一个圆，总人数为 num_people。每个人与除自己外的一个人握手，所以总共会有 num_people / 2 次握手。
将握手的人之间连线，请你返回连线不会相交的握手方案数。
由于结果可能会很大，请你返回答案 模 10^9+7 后的结果。
示例1：
输入：num_people = 2 输出：1
示例2：
输入：num_people = 4 输出：2 解释：总共有两种方案，第一种方案是 [(1,2),(3,4)] ，第二种方案是 [(2,3),(4,1)] 。
示例3：
输入：num_people = 6 输出：5
示例4：
输入：num_people = 8 输出：14
提示：
- 2 <= num_people <= 1000
- num_people % 2 == 0
如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=1259
解题思路分析：
开始看到本题时本没有太多的思路，不过仔细一想，其实并没有那么复杂，要想满足不相交握手，其实就是将人分割成 (num_people / 2) 这么多组，很像切蛋糕，每一组都只有2个人，他们2个人之间握手一定不会影响到其他组。再反过来想，当前人可以与谁进行握手？最简单的想法应该是和相邻的人握手，这肯定是可以的。如果隔着一个人跟下一个人握手是绝对不行的，因为中间那个被隔开的人不论再与谁握手都会发生交叉。接下来，如果隔着2个人与下一个人握手，那么是可行的，因为中间被隔开的2个人可以进行握手并且不会与当前握手交叉。因此我们可以得到一个结论，只要当前人与握手对象之间存在偶数个人，那么即可以握手。
比如一共有8个人（编号0-7），0应该可以与1，3，5，7四人握手是成立的。我们设定握手的对象为i，当0和i进行握手后，其实是将所有人分成了2个部分，分别是0和i中间的部分，以及i之后的部分，即分为了i-1个人和num_people-i-1个人，假如当前i为3，即第0个人与第3个人握手之后，可以将人群分为2人和4人，这时我们可以将2人和4人分别扔给递归子问题去求解，求解方式与当前解法是相同的。两者的乘积是当前的结果。递归的结束条件是当前总人数只有2人时，可以直接返回1。
因此，循环所有握手的可能（1，3，5，7），分别递归求出每种可能的解，求和即是答案。设f(n)代表：总共n个人能产生的不交叉握手方案数。
f(8)= f(0) * f(6) // 0与1握手后，剩下的人被分为0人和6人2组 + f(2) * f(4) // 0与3握手，剩下的人被分为2人和4人2组 + f(4) * f(2) // 0与5握手，剩下的人被分为4人和2人2组 + f(6) * f(0) // 0与7握手，剩下的人被分为6人和0人2组
实现代码：
int[] memo; // 记忆数组
public int numberOfWays(int num_people) {
memo=new int[1+num_people]; // 初始化记忆数组
return (int)help(num_people); // 递归求解
}
long help(int num_people){
// 如果记忆数组存在值，直接发挥
if(memo[num_people]>0){
return memo[num_people];
}
// 如果总人数小于等于2，返回1
if(num_people<=2) return 1;
// 返回结果
long res=0;
// 从相邻人开始循环可能握手的人（相隔人数为偶数）
for(int i=1;i<num_people;i+=2){
// 握手后将人分为两部分，两部分递归求解的乘积加入返回结果
res+=(help(i-1)*help(num_people-i-1))%1000000007;
}
// 将结果存入记忆数组
memo[num_people]=(int)(res%1000000007);
return memo[num_people];
} 本题解法执行时间为8ms。
Runtime: 8 ms, faster than 94.50% of Java online submissions for Handshakes That Don’t Cross.
Memory Usage: 33.1 MB, less than 100.00% of Java online submissions for Handshakes That Don’t Cross.
本网站文章均为原创内容，并可随意转载，但请标明本文链接如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/leetcode-1259-handshakes-that-dont-cross-解题思路分析/