题目描述
偶数 个人站成一个圆,总人数为 num_people
。每个人与除自己外的一个人握手,所以总共会有 num_people / 2
次握手。
将握手的人之间连线,请你返回连线不会相交的握手方案数。
由于结果可能会很大,请你返回答案 模 10^9+7
后的结果。
样例
输入:num_people = 2
输出:1
输入:num_people = 4
输出:2
解释:总共有两种方案,第一种方案是 [(1,2),(3,4)] ,第二种方案是 [(2,3),(4,1)] 。
输入:num_people = 6
输出:5
输入:num_people = 8
输出:14
限制
2 <= num_people <= 1000
num_people % 2 == 0
算法
(动态规划) $O(n^2)$
- $f(i)$ 表示 $i$ 个时的方案数,其中 $i$ 为偶数。
- 初始时 $f(0) = 1$,其余为 0。
- 转移时,枚举第 $i$ 个人和编号为 $j$ 的人握手,其中 $j$ 为奇数,则 $f(i) = f(i) + f(j - 1) * f(i - j - 1)$。这个公式的含义是,如果第 $i$ 个人与第 $j$ 个人握手,则前 $j - 1$ 个人的握手问题为子问题,共有 $f(j - 1)$ 种方案;
[j + 1, i - 1]
为 $i - j - 1$ 个人握手的问题,共有 $f(i - j - 1)$ 种方案,根据乘法原理和加法原理,对于每个 $j$,我们需要累加答案 $f(j - 1) \cdot f(i - j - 1)$。 - 最终答案为 $f(n)$。
时间复杂度
- 共有 $O(n)$ 个状态,每个状态需要 $O(n)$ 的时间转移,故总时间复杂度为 $O(n^2)$。
空间复杂度
- 需要额外 $O(n)$ 的空间存储状态。
C++ 代码
class Solution {
public:
#define LL long long
int numberOfWays(int num_people) {
const int mod = 1000000007;
vector<int> f(num_people + 1, 0);
f[0] = 1;
for (int i = 2; i <= num_people; i += 2)
for (int j = 1; j < i; j += 2)
f[i] = (f[i] + (LL)(f[j - 1]) * f[i - j - 1] % mod) % mod;
return f[num_people];
}
};