LeetCode 1259. 不相交的握手（DP）

文章目录

• • 1. 题目
  • 2. 解题

1. 题目

偶数 个人站成一个圆，总人数为 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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/handshakes-that-dont-cross
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2. 解题

• 考虑 n 个人， 1号跟其他的偶数号握手才可以，不然有落单的，总计 n/2 次
• 1号跟另一个人握手，把人群分成了两个子问题，两边的数量相乘即可，n-2人，分成2半（0，n-2）(2, n-4)…

class Solution { public:int numberOfWays(int num_people) {if(num_people == 2) return 1;if(num_people == 4) return 2;vector<long long> dp(num_people+1, 0);dp[0] = 1;dp[2] = 1;dp[4] = 2;for(int i = 6; i <= num_people; i += 2){for(int j = 0; j < i/2; ++j){dp[i] = (dp[i]+dp[2*j]*dp[i-2-2*j])%1000000007;}}return dp[num_people];} };

28 ms 6.6 MB

---

我的CSDN博客地址 https://michael.blog.csdn.net/

长按或扫码关注我的公众号（Michael阿明），一起加油、一起学习进步！

总结

以上是生活随笔为你收集整理的LeetCode 1259. 不相交的握手（DP）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。