LeetCode 1259. 不相交的握手

约 5 分钟
文章信息 6 个分类 2 个标签
分类
LeetCode CodeTop 困难 未解决 1-2 字节跳动
标签
动态规划 数学
目录

题目描述

✅ 1259. 不相交的握手

题意分析

numPeople 个人围成一圈（人数保证是偶数），每个人恰好和另一个人握一次手，要求任意两次握手对应的弦在圆内不相交，问有多少种不同的握手方案，结果对 $10^9+7$ 取模。

「围成一圈」加上「不相交」是全部结构来源。把人按顺序编号 $0, 1, \ldots, numPeople-1$ 排在圆周上，一次握手就是一条连接两点的弦。两条弦不相交，等价于它们对应的两对端点在圆周上不「交错」。

关键推论：如果 0 号和 k 号握手，这条弦把剩下的人切成两段互不相通的圆弧——编号 $1 \sim k-1$ 是一段，$k+1 \sim numPeople-1$ 是另一段。任何跨越这条弦的握手都必然与它相交，所以两段内部各自独立配对，互不影响。这就是把大问题切成两个同类子问题的依据。

再推一步：既然两段内部必须自我配对，每段的人数就必须是偶数，也就是 $k$ 必须是奇数。这个奇偶约束会直接决定枚举的形式。

数据规模：numPeople 不超过 1000，也就是最多 500 对握手。$O(n^2)$ 的规模约 25 万次运算，完全可行；答案要取模说明数值会爆炸，暗示这是一个增长极快的计数量。

边界：numPeople 为 0（空圈，方案数 1）、为 2（只有一种）、结果超出 32 位需要用更宽的类型做中间运算。

解法：卡特兰数 DP

核心思路

固定 0 号的握手对象。若 0 号与编号 2j+1 的人握手，这条弦把其余人分成两段：中间有 2j 人，另一侧有 2(i-1-j) 人。两段不能跨过这条弦连接，只能各自在内部形成不相交配对，因此方案数相乘。

用“握手对数”定义状态：dp[i] 表示 2i 个人的不相交完全配对方案数。枚举 0 号弦两侧的对数，得到递推式 $dp[i]=\sum_{j=0}^{i-1}dp[j]dp[i-1-j]$。

初值 dp[0] = 1 表示空区间有一种配对方式。它是乘法单位元，使某一侧没有人的边界也能直接使用同一递推式。

不变量：计算 dp[i] 时，所有更小对数的状态已经是正确答案。 正序计算保证转移来源可用。

正确性说明：每个合法方案中 0 号的握手对象唯一，所以它恰好落入一个 j；被该弦分开的两侧必须独立配对，对应乘积 dp[j] * dp[i-1-j]。反过来，两侧任意合法方案都能唯一组合成一个整体方案，因此递推既不重复也不遗漏。

计数增长很快。两个已取模的状态相乘必须使用 64 位，并在每次乘加后立即取模，避免累计和溢出。

解题步骤

  1. 令 pairs = numPeople / 2，状态只记录对数。
  2. 创建 dp[0..pairs]，设置 dp[0] = 1。
  3. 对 i = 1..pairs，枚举 j = 0..i-1，累加 dp[j] * dp[i-1-j] 并取模。
  4. 返回 dp[pairs]。

以 numPeople = 6 为例，pairs = 3：

  • dp[1] = dp[0] * dp[0] = 1；
  • dp[2] = dp[0] * dp[1] + dp[1] * dp[0] = 2；
  • dp[3] = dp[0] * dp[2] + dp[1] * dp[1] + dp[2] * dp[0] = 5。

因此答案为 5。边界 numPeople = 2 对应 dp[1] = 1；概念上的空区间由 dp[0] = 1 处理。

代码实现

class Solution {
    private static final int MOD = 1_000_000_007;

    public int numberOfWays(int numPeople) {
        int pairs = numPeople / 2;
        long[] dp = new long[pairs + 1];
        dp[0] = 1;

        for (int i = 1; i <= pairs; i++) {
            for (int left = 0; left < i; left++) {
                int right = i - 1 - left;
                dp[i] = (dp[i] + dp[left] * dp[right]) % MOD;
            }
        }
        return (int) dp[pairs];
    }
}

func numberOfWays(numPeople int) int {
	const mod int64 = 1_000_000_007
	pairs := numPeople / 2
	dp := make([]int64, pairs+1)
	dp[0] = 1

	for i := 1; i <= pairs; i++ {
		for left := 0; left < i; left++ {
			right := i - 1 - left
			dp[i] = (dp[i] + dp[left]*dp[right]) % mod
		}
	}
	return int(dp[pairs])
}

复杂度分析

设 p = numPeople / 2。

  • 时间复杂度： $O(p^2)$。状态 i 枚举 i 种切分。
  • 空间复杂度： $O(p)$，用于保存动态规划数组。

关键点总结

  • 圆上不相交配对的关键结构是：固定一条弦后，两侧成为独立的同类子问题。
  • dp[i] 以“对数”而非人数为状态，奇偶约束随之消失。
  • 按 0 号的唯一握手对象分类，给出了递推不重不漏的依据。
  • dp[0] = 1 是空侧的乘法单位元。
  • 模乘使用 64 位，并在每次累加后取模。

易错点总结

  • 把 0 号与偶数编号配对： 这会在弦的一侧留下奇数个人，无法内部完成配对。
  • 转移漏掉 -1： 写成 dp[left] * dp[i-left] 会读取尚未完成的 dp[i]。
  • 将 dp[0] 留为 0： 所有状态都会从 0 推出，numPeople = 6 会错误返回 0。
  • 用 32 位保存乘积： 两个接近模数的状态相乘会立即溢出。
  • 内层全部累加后才取模： 最多 500 个接近 $10^{18}$ 的乘积之和会超过 64 位范围。

相似题目

题目 难度 考察点
96. 不同的二叉搜索树 中等 划分依据换成「谁当根」，是同一卷积递推的最裸原型
22. 括号生成 中等 数量同为卡特兰数，但要求构造全部方案，需回溯而非计数
95. 不同的二叉搜索树 II 中等 在计数递推之上返回所有树形，左右子树结果要做笛卡尔积
241. 为运算表达式设计优先级 中等 按运算符切分左右两段，切分点枚举形式相同但要合并具体取值