LeetCode 1259. 不相交的握手

2022-04-11 HGNULB 约 4 分钟

文章信息 7 个分类 2 个标签

分类

LeetCode CodeTop 困难未解决会员题 1-2 字节

题目描述

✅ 1259. 不相交的握手

题意分析

偶数个人沿圆周按固定顺序站立，每个人恰好与另一人握手。每对握手画成圆内的一条连线，所有连线都不能相交，求全部不同配对方案数，对 10^9 + 7 取模。

人的位置和身份固定，只选择谁与谁配对；不是重新安排座位，也不是随便将人数除成若干组。某个人选定搭档后，两人的连线会限制其余人的配对范围。

解法：卡特兰数 DP

核心思路

[!blue]

固定圆周上的第一个人，枚举他的搭档。这条握手连线将剩余人分到两个连续区域。如果把一侧的人与另一侧的人配对，连线就会跨过固定握手，因此两侧必须各自完成配对，人数也都必须为偶数。

按握手对数定义状态：dp[i] 表示 2i 个人的不相交方案数。固定第一人的搭档后已经消耗一对，若一侧剩 left 对，另一侧就是 i - 1 - left 对。两侧的合法选择可以任意组合，方案数相乘，得到 dp[left] * dp[i - 1 - left]。

left 从零到 i - 1，恰好对应第一人所有能够留下偶数两侧人数的搭档。每个完整方案中，第一人的搭档唯一，所以按这个搭档分类不会重复；每个合法方案也必定属于某一种划分，因此将各项相加不会漏计。

空的一侧无需再配对，只有一种完成方式，故 dp[0] = 1。较大状态只依赖更小对数，按对数递增即可计算，这就是卡特兰数递推。计数很大，两个取模后状态相乘仍需 64 位，并在每次累加后立即取模。

解题步骤

令总对数 pairs = numPeople / 2，创建状态数组，设置 dp[0] = 1。

从一对开始计算当前 i 对人的答案。

枚举固定握手一侧的对数 left，另一侧取 right = i - 1 - left。

用 64 位将 dp[left] * dp[right] 加入 dp[i]，随即取模。

返回 dp[pairs]。

代码实现

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

    public int numberOfWays(int numPeople) {
        int pairs = numPeople / 2;
        // dp[i] 表示 2i 人、即 i 对人的不相交握手方案数。
        long[] dp = new long[pairs + 1];

        // 空的一侧有一种完成方式，作为两侧相乘的单位元。
        dp[0] = 1;

        for (int i = 1; i <= pairs; i++) {
            for (int left = 0; left < i; left++) {
                // 固定的握手已经消耗一对，剩余两侧合计 i-1 对。
                int right = i - 1 - left;

                // 两个状态用 64 位相乘，每次累加后立即取模。
                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[i] 表示 2i 人、即 i 对人的不相交握手方案数。
    dp := make([]int64, pairs+1)
    // 空的一侧有一种完成方式，作为两侧相乘的单位元。
    dp[0] = 1

    for i := 1; i <= pairs; i++ {
        for left := 0; left < i; left++ {
            // 固定的握手已经消耗一对，剩余两侧合计 i-1 对。
            right := i - 1 - left
            // 两个状态用 64 位相乘，每次累加后立即取模。
            dp[i] = (dp[i] + dp[left]*dp[right]) % mod
        }
    }
    return int(dp[pairs])
}

复杂度分析

时间复杂度：$O(p^2)$，p 为人数的一半，第 i 个状态枚举 i 个划分，累计为平方级。

空间复杂度：$O(p)$，保存从零对到 p 对的计数。

关键点总结

[!green]

固定一个人的搭档，连线将剩余问题分成不能跨越的两个独立区域。

两侧方案组合用乘法，不同搭档的类别用加法。

两侧合计少一对，因为固定握手已经占用两个人。

空区域计为一种完成方式，才能正确参与乘积。

易错点总结

[!yellow]

任意枚举搭档而忽略两侧人数奇偶，某一侧剩奇数人就不能内部配对。

将两侧方案数相加，遗漏了它们可以独立组合形成不同完整方案。

右侧对数写成 i - left，没有扣掉最先固定的一对。

dp[0] 为零，含空侧的项全部消失，后面的计数无法建立。

用 32 位计算两个模数范围内计数的乘积，取模前就可能溢出。

很多乘积全部累加后才取模，64 位累计也可能超范围，应每项及时取模。

相似题目

题目	难度	关联与区别
96. 不同的二叉搜索树	中等	固定一个配对后圆环被分成两个独立区域，方案数相乘再求和，形成卡特兰递推。
22. 括号生成	中等	不交叉握手与合法括号都具有嵌套或并列的分解结构，计数可相互对应。

转载与许可

作者 HGNULB

链接 https://hgnulb.github.io/blog/2022/35090337

许可本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！