LeetCode 1259 Handshakes That Dont Cross 全解卡特兰数与动态规划的三种实现路径【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode本篇围绕 leetcode 仓库中 articles/handshakes-that-dont-cross.md 展开系统讲解不交叉握手Handshakes That Dont Cross的计数问题。你将掌握如何把圆桌上的握手场景抽象为将子问题拆分为两个独立子问题的递归结构并依次实现自底向上 DP、自顶向下记忆化搜索与基于模逆元的卡特兰数公式三种解法同时理解模运算与 64 位整数转换等工程细节。问题背景与前置知识numPeople个偶数人数站成一个圆圈每个人必须与另外一个人握手且任意两条握手连线不能交叉。求总的合法握手方案数结果对10^9 7取模。在动手实现前需要具备三项基础能力原文档 Prerequisites 部分动态规划Dynamic Programming能够用递推关系从较小的子问题构建出完整解卡特兰数Catalan Numbers能识别出计数非交叉配对方案这类问题其答案正是卡特兰序列模运算Modular Arithmetic会使用取模防止整数溢出并能计算模逆元以支持除法运算。这些前置知识并非孤立的——本仓库的姊妹题 unique-binary-search-trees.md统计1..n能构成多少种不同结构的二叉搜索树同样以卡特兰数为核心两篇文章的递推骨架完全同构建议对照阅读。核心直觉一次握手如何切分圆设想0号人与k号人握手k必须为奇数因为握手两侧各需要偶数人数才能继续两两配对。此时圆被这条弦切成两个互相独立的区域区域一0与k之间的人区域二k与最后一人之间的人。两条区域内部的握手互不干扰、也不会与0-k这条连线交叉因此该配置下的总方案数等于两个区域各自方案数的乘积。对0号人的所有合法搭档k求和就得到了完整的递推关系——这正是卡特兰数的经典递推它统计的正是非交叉配对结构。仓库源码 javascript/0096-unique-binary-search-trees.js 中统计唯一 BST 数量的 DFS 写的是total dfs(i) * dfs(n - 1 - i)选一个根后左子树放i个节点、右子树放n-1-i个节点。这与握手问题固定0号人的搭档后两侧分别剩下j对与i-j-1对是同一套乘法原理可互相印证。解法一自底向上动态规划Bottom-Up DP算法思路用dp[i]表示2*i个人的合法握手方案数初始化dp[0] 1零个人只有一种空安排对i从1到numPeople / 2枚举固定一人的搭档将两侧子问题合并即dp[i] sum(dp[j] * dp[i - j - 1])其中j从0到i - 1每一步都及时取模防止中间结果溢出返回dp[numPeople / 2]。以numPeople 4即n 2为例dp[1] dp[0]*dp[0] 1dp[2] dp[0]*dp[1] dp[1]*dp[0] 2与卡特兰数C(2) 2一致即 4 人恰好只有 2 种不交叉握手方案。多语言实现class Solution: def numberOfWays(self, numPeople: int) - int: m 1000000007 dp [0] * (numPeople // 2 1) dp[0] 1 for i in range(1, numPeople // 2 1): for j in range(i): dp[i] dp[j] * dp[i - j - 1] dp[i] % m return dp[numPeople // 2]class Solution { private static int m 1000000007; public int numberOfWays(int numPeople) { int[] dp new int[numPeople / 2 1]; dp[0] 1; for (int i 1; i numPeople / 2; i) { for (int j 0; j i; j) { dp[i] (long) dp[j] * dp[i - j - 1] % m; dp[i] % m; } } return dp[numPeople / 2]; } }class Solution { const static int m 1000000007; public: int numberOfWays(int numPeople) { vectorint dp(numPeople / 2 1); dp[0] 1; for (int i 1; i numPeople / 2; i) { for (int j 0; j i; j) { (dp[i] (long long)dp[j] * dp[i - j - 1] % m) % m; } } return dp[numPeople / 2]; } };class Solution { /** * param {number} numPeople * return {number} */ numberOfWays(numPeople) { const m 1000000007n; const n Math.floor(numPeople / 2); const dp new Array(n 1).fill(0n); dp[0] 1n; for (let i 1; i n; i) { for (let j 0; j i; j) { dp[i] dp[j] * dp[i - j - 1]; dp[i] % m; } } return Number(dp[n]); } }func numberOfWays(numPeople int) int { m : 1000000007 n : numPeople / 2 dp : make([]int, n1) dp[0] 1 for i : 1; i n; i { for j : 0; j i; j { dp[i] dp[j] * dp[i-j-1] % m dp[i] % m } } return dp[n] }class Solution { fun numberOfWays(numPeople: Int): Int { val m 1000000007L val n numPeople / 2 val dp LongArray(n 1) dp[0] 1L for (i in 1..n) { for (j in 0 until i) { dp[i] dp[j] * dp[i - j - 1] % m dp[i] % m } } return dp[n].toInt() } }class Solution { func numberOfWays(_ numPeople: Int) - Int { let m 1000000007 let n numPeople / 2 var dp Int dp[0] 1 for i in 1...n { for j in 0..i { dp[i] dp[j] * dp[i - j - 1] % m dp[i] % m } } return dp[n] } }impl Solution { pub fn number_of_ways(num_people: i32) - i32 { let m: i64 1_000_000_007; let n (num_people / 2) as usize; let mut dp vec![0i64; n 1]; dp[0] 1; for i in 1..n { for j in 0..i { dp[i] dp[j] * dp[i - j - 1] % m; dp[i] % m; } } dp[n] as i32 } }注意 JavaScript 与 Kotlin、Rust 实现使用BigInt或Long/i64承载中间乘积Java、C、Go 则在乘法前显式转成 64 位整数这正是下文常见陷阱中溢出问题的标准规避方式。复杂度时间复杂度$O(numPeople^2)$——外层循环n次、内层求和平均n/2次空间复杂度$O(numPeople)$——仅需一张长度为numPeople/2 1的 DP 表。解法二自顶向下动态规划记忆化搜索算法思路同样的递推关系换用递归 缓存实现从目标规模numPeople/2出发需要哪个子结果就递归计算哪个并用dp数组缓存已算过的值避免重复计算。这种写法更贴合问题结构——为第一个人选搭档、递归解决两侧子问题。初始化dp数组为-1表示未计算并令dp[0] 1定义递归函数calculateDP(i)若dp[i]已计算则直接返回否则令dp[i] sum(calculateDP(j) * calculateDP(i-j-1))j从0到i-1取模后缓存并返回调用calculateDP(numPeople / 2)返回结果。多语言实现class Solution: def numberOfWays(self, numPeople: int) - int: m 1000000007 dp [-1] * (numPeople // 2 1) dp[0] 1 def calculate_dp(i): if dp[i] ! -1: return dp[i] dp[i] 0 for j in range(i): dp[i] calculate_dp(j) * calculate_dp(i - j - 1) dp[i] % m return dp[i] return calculate_dp(numPeople // 2)class Solution { private static int m 1000000007; int[] dp; public int numberOfWays(int numPeople) { dp new int[numPeople / 2 1]; Arrays.fill(dp, -1); dp[0] 1; return calculateDP(numPeople / 2); } private int calculateDP(int i) { if (dp[i] ! -1) { return dp[i]; } dp[i] 0; for (int j 0; j i; j) { dp[i] (long) calculateDP(j) * calculateDP(i - j - 1) % m; dp[i] % m; } return dp[i]; } }class Solution { const static int m 1000000007; public: int numberOfWays(int numPeople) { vectorint dp(numPeople / 2 1, -1); dp[0] 1; functionint(int) calculateDP - int { if (dp[i] ! -1) { return dp[i]; } dp[i] 0; for (int j 0; j i; j) { (dp[i] (long long)calculateDP(j) * calculateDP(i - j - 1) % m) % m; } return dp[i]; }; return calculateDP(numPeople / 2); } };class Solution { /** * param {number} numPeople * return {number} */ numberOfWays(numPeople) { const m 1000000007n; const n Math.floor(numPeople / 2); const dp new Array(n 1).fill(-1n); dp[0] 1n; const calculate_dp (i) { if (dp[i] ! -1n) { return dp[i]; } dp[i] 0n; for (let j 0; j i; j) { dp[i] calculate_dp(j) * calculate_dp(i - j - 1); dp[i] % m; } return dp[i]; }; return Number(calculate_dp(n)); } }func numberOfWays(numPeople int) int { m : 1000000007 n : numPeople / 2 dp : make([]int, n1) for i : range dp { dp[i] -1 } dp[0] 1 var calculateDP func(i int) int calculateDP func(i int) int { if dp[i] ! -1 { return dp[i] } dp[i] 0 for j : 0; j i; j { dp[i] calculateDP(j) * calculateDP(i-j-1) % m dp[i] % m } return dp[i] } return calculateDP(n) }class Solution { private val m 1000000007L private lateinit var dp: LongArray fun numberOfWays(numPeople: Int): Int { val n numPeople / 2 dp LongArray(n 1) { -1L } dp[0] 1L return calculateDP(n).toInt() } private fun calculateDP(i: Int): Long { if (dp[i] ! -1L) { return dp[i] } dp[i] 0L for (j in 0 until i) { dp[i] calculateDP(j) * calculateDP(i - j - 1) % m dp[i] % m } return dp[i] } }class Solution { func numberOfWays(_ numPeople: Int) - Int { let m 1000000007 let n numPeople / 2 var dp Int dp[0] 1 func calculateDP(_ i: Int) - Int { if dp[i] ! -1 { return dp[i] } dp[i] 0 for j in 0..i { dp[i] calculateDP(j) * calculateDP(i - j - 1) % m dp[i] % m } return dp[i] } return calculateDP(n) } }impl Solution { pub fn number_of_ways(num_people: i32) - i32 { let m: i64 1_000_000_007; let n (num_people / 2) as usize; let mut dp vec![-1i64; n 1]; dp[0] 1; fn calculate_dp(i: usize, dp: mut Veci64, m: i64) - i64 { if dp[i] ! -1 { return dp[i]; } dp[i] 0; for j in 0..i { dp[i] calculate_dp(j, dp, m) * calculate_dp(i - j - 1, dp, m) % m; dp[i] % m; } dp[i] } calculate_dp(n, mut dp, m) as i32 } }这一递归形态与仓库中 javascript/0096-unique-binary-search-trees.js 的dfs(n)缓存写法几乎一一对应可以放在一起对比学习握手问题把第一个人选搭档当作 BST 里的选根节点两侧子问题即左右子树。复杂度时间复杂度$O(numPeople^2)$——每个状态至多计算一次每次计算需枚举O(i)个分割点空间复杂度$O(numPeople)$——DP 缓存数组 递归栈深度O(n)。解法三卡特兰数公式与模逆元算法思路非交叉握手方案数恰好等于第n numPeople / 2个卡特兰数。卡特兰数存在闭式递推$$C(n) C(n-1) \cdot \frac{2(2n-1)}{n1}$$可以线性迭代出结果空间上只需预计算模逆元数组。由于10^9 7是素数1..n1范围内每个数的模逆元可通过如下递推公式求得$$inv[i] m - (m / i) \cdot inv[m % i] % m$$实现步骤用上述恒等式预计算1到n1的模逆元inv[1] 1初始化C 1代表C(0)对i从0到n-1令C C * 2 * (2*i 1) * inv[i 2] % m返回C。这里用2*(2*i1)取代公式中的2*(2n-1)步进变量不同配合inv[i2]完成对n1的除法本质相同。多语言实现class Solution: def numberOfWays(self, numPeople: int) - int: m 1000000007 n numPeople // 2 inv [None] * (n2) inv[1] 1 for i in range(2, n2): k m // i r m % i inv[i] m - k * inv[r] % m C 1 for i in range(n): C 2 * (2 * i 1) * inv[i 2] * C % m return Cclass Solution { private static int m 1000000007; private int mul(int a, int b) { return (int) ((long) a * b % m); } public int numberOfWays(int numPeople) { int n numPeople / 2; int[] inv new int[numPeople / 2 2]; inv[1] 1; for (int i 2; i n 2; i) { int k m / i, r m % i; inv[i] m - mul(k, inv[r]); } int C 1; for (int i 0; i n; i) { C mul(mul(2 * (2 * i 1), inv[i 2]), C); } return C; } }class Solution { const int m 1000000007; int mul(int a, int b) { return (long long)a * b % m; } public: int numberOfWays(int numPeople) { int n numPeople / 2; vectorint inv(n 2); inv[1] 1; for (int i 2; i n 2; i) { int k m / i, r m % i; inv[i] m - mul(k, inv[r]); } int C 1; for (int i 0; i n; i) { C mul(mul(2 * (2 * i 1), inv[i 2]), C); } return C; } };class Solution { /** * param {number} numPeople * return {number} */ numberOfWays(numPeople) { const m 1000000007n; const n Math.floor(numPeople / 2); const inv new Array(n 2); inv[1] 1n; for (let i 2; i n 2; i) { const bi BigInt(i); const k m / bi; const r m % bi; inv[i] (m - ((k * inv[Number(r)]) % m)) % m; } let C 1n; for (let i 0; i n; i) { C (((2n * BigInt(2 * i 1) * inv[i 2]) % m) * C) % m; } return Number(C); } }func numberOfWays(numPeople int) int { m : 1000000007 n : numPeople / 2 inv : make([]int, n2) inv[1] 1 mul : func(a, b int) int { return int(int64(a) * int64(b) % int64(m)) } for i : 2; i n2; i { k : m / i r : m % i inv[i] m - mul(k, inv[r]) } C : 1 for i : 0; i n; i { C mul(mul(2*(2*i1), inv[i2]), C) } return C }class Solution { private val m 1000000007L private fun mul(a: Long, b: Long): Long { return a * b % m } fun numberOfWays(numPeople: Int): Int { val n numPeople / 2 val inv LongArray(n 2) inv[1] 1L for (i in 2 until n 2) { val k m / i val r (m % i).toInt() inv[i] m - mul(k, inv[r]) } var C 1L for (i in 0 until n) { C mul(mul((2 * (2 * i 1)).toLong(), inv[i 2]), C) } return C.toInt() } }class Solution { func numberOfWays(_ numPeople: Int) - Int { let m 1000000007 let n numPeople / 2 var inv Int inv[1] 1 func mul(_ a: Int, _ b: Int) - Int { return Int(Int64(a) * Int64(b) % Int64(m)) } for i in 2..(n 2) { let k m / i let r m % i inv[i] m - mul(k, inv[r]) } var C 1 for i in 0..n { C mul(mul(2 * (2 * i 1), inv[i 2]), C) } return C } }impl Solution { pub fn number_of_ways(num_people: i32) - i32 { let m: i64 1_000_000_007; let n (num_people / 2) as usize; let mut inv vec![0i64; n 2]; inv[1] 1; let mul |a: i64, b: i64| - i64 { a * b % m }; for i in 2..(n 2) { let k m / i as i64; let r (m % i as i64) as usize; inv[i] m - mul(k, inv[r]); } let mut c: i64 1; for i in 0..n { c mul(mul(2 * (2 * i as i64 1), inv[i 2]), c); } c as i32 } }复杂度时间复杂度$O(numPeople)$——预计算逆元一次线性扫描主循环再次线性扫描空间复杂度$O(numPeople)$——逆元数组长度n 2。相比前两种 $O(numPeople^2)$ 的 DP 解法这是本题的最优渐进复杂度。三种解法对比解法思路时间复杂度空间复杂度适用场景自底向上 DP迭代填表按规模从小到大$O(n^2)$$O(n)$实现直观、无递归栈风险自顶向下 DP递归 记忆化缓存$O(n^2)$$O(n)$代码与问题结构一一对应易调试卡特兰数公式闭式递推 模逆元$O(n)$$O(n)$追求最优时间复杂度的场景三者返回结果完全一致均为第numPeople/2个卡特兰数区别在于如何组织子问题的求解顺序以及是否显式利用数学闭式。若输入规模较小DP 写法已足够若numPeople接近题目上限卡特兰数公式更稳。常见陷阱1. 忘记在每一步取模方案数呈指数级增长若只在最后取模中间值早已溢出标准整型。取模必须紧跟每次乘法和加法之后让中间结果始终保持在可表示范围内。2. DP 递推下标出错递推dp[i] sum(dp[j] * dp[i-j-1])中求和范围是j 0到j i - 1且i-j-1必须始终非负。循环边界或下标计算的差一错误off-by-one会导致越界访问或在求和时遗漏项。3. 未识别出卡特兰数模式本题是卡特兰数的经典应用但不少求解者会试图从零推导递推而绕远路。关键洞察始终是第一个人与第k个人握手会把剩余的人分成两个独立子问题——理解这一点能同时简化实现与调试。4. 模运算中的整数溢出dp[j] * dp[i-j-1]中每个因子都小于10^9乘积可能超过 32 位整型上限。Java、C、Go 必须在乘法前显式提升为 64 位long/long long/int64再执行取模否则会静默溢出得到错误结果。对应地JavaScript 实现统一使用BigIntKotlin/Swift/Rust 使用Long/Int64/i64。5. 模逆元计算错误卡特兰数闭式公式涉及除法在模算术中除以等价于乘以模逆元。逆元递推式inv[i] m - (m/i) * inv[m%i] % m必须严格按运算顺序实现先乘、取模、再用m相减任何一处优先级写错都会导致结果错误。此外还要保证inv[1] 1这一初值。在仓库中继续深入articles/handshakes-that-dont-cross.md本篇所依据的原始讲解文档articles/unique-binary-search-trees.md同为卡特兰数家族的姊妹题LeetCode 96可对照体会非交叉配对与二叉搜索树计数的同一数学结构javascript/0096-unique-binary-search-trees.js仓库中该题的记忆化 DFS 源码其dfs(i) * dfs(n - 1 - i)与本文dp[j] * dp[i-j-1]递推同构javascript/0095-unique-binary-search-trees-ii.js唯一 BST 的构造版输出所有树可进一步体会乘法原理拆分左右子问题的推广形态。建议学习路径先用自底向上 DP 跑通逻辑 → 用记忆化版本对照理解递归结构 → 最后用卡特兰数公式压缩时间复杂度并顺手复习模逆元的线性递推这套组合对面试中计数类 取模题型非常通用。【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考