LeetCode 1259. 不相交的握手

Categories:

题目描述
思路分析
1. 解法一：卡特兰数 DP（推荐）
相似题目

题目描述

✅ 1259. 不相交的握手

思路分析

解法一：卡特兰数 DP（推荐）

核心思路：

设 n = numPeople / 2，问题等价于合法括号序列数量。

定义 dp[i] 表示 i 对握手的方案数。

转移：dp[i] = sum(dp[j] * dp[i - 1 - j])。

复杂度分析：

时间复杂度：O(n^2)。

空间复杂度：O(n)。

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

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

        for (int i = 1; i <= n; i++) {
            long sum = 0;
            for (int j = 0; j < i; j++) {
                sum = (sum + dp[j] * dp[i - 1 - j]) % MOD;
            }
            dp[i] = sum;
        }
        return (int) dp[n];
    }
}

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

    for i := 1; i <= n; i++ {
        var sum int64
        for j := 0; j < i; j++ {
            sum = (sum + dp[j]*dp[i-1-j]) % mod
        }
        dp[i] = sum
    }
    return int(dp[n])
}

相似题目

题目	难度	考察点
22. 括号生成	中等	卡特兰数
96. 不同的二叉搜索树	中等	卡特兰数
241. 为运算表达式设计优先级	中等	分治
1541. 平衡括号字符串的最少插入次数	中等	计数
856. 括号的分数	中等	栈

本文作者: HGNULB

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