LeetCode 1259. 不相交的握手（DP）
LeetCode 1259. 不相交的握手（DP）
Michael阿明
发布于 2021-02-19 10:47:23
发布于 2021-02-19 10:47:23
文章被收录于专栏：Michael阿明学习之路
文章目录
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
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2020/08/02 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
