卡特兰数在LeetCode刷题中的5种经典应用场景（附Python代码）

卡特兰数在LeetCode刷题中的5种经典应用场景附Python代码卡特兰数Catalan Numbers是组合数学中一个既优美又实用的数列它在算法问题中扮演着重要角色。对于准备技术面试的开发者来说掌握卡特兰数的应用场景能快速解决一类特定问题。本文将聚焦LeetCode高频题型通过5个经典场景展示如何识别卡特兰数特征并实现高效解题。1. 括号生成问题LeetCode第22题「括号生成」是卡特兰数的典型应用。要求生成所有有效的n对括号组合其总数正是第n个卡特兰数。问题特征识别需要生成所有合法排列而非计数时通常需要回溯法仅需计数时可直接套用卡特兰数公式合法条件任意前缀中左括号数≥右括号数Python实现模板def generateParenthesis(n): def backtrack(s, left, right): if len(s) 2*n: res.append(s) return if left n: backtrack(s(, left1, right) if right left: backtrack(s), left, right1) res [] backtrack(, 0, 0) return res # 计数版卡特兰数公式 def catalan(n): from math import comb return comb(2*n, n) // (n 1)复杂度对比方法时间复杂度空间复杂度回溯法O(4^n/√n)O(n)公式法O(1)O(1)提示面试中若只需计数直接给出卡特兰数结果能显著提升解题效率2. 二叉树形态计数LeetCode第96题「不同的二叉搜索树」要求计算由n个节点组成的BST数量这正是卡特兰数的定义。问题转化技巧选定根节点后左右子树节点数之和为n-1总方案数Σ(左子树方案×右子树方案)递推式与卡特兰数定义完全一致动态规划解法def numTrees(n): dp [0]*(n1) dp[0] dp[1] 1 for i in range(2, n1): for j in range(i): dp[i] dp[j] * dp[i-j-1] return dp[n] # 数学优化版 def numTrees_math(n): from math import comb return comb(2*n, n) // (n 1)典型变式题目LeetCode 95生成所有BST需要实际构建树LeetCode 894所有可能的满二叉树3. 栈排序问题栈操作相关的计数问题往往隐藏着卡特兰数。例如「合法的出栈顺序总数」就是经典场景。LeetCode关联题目验证栈序列验证合法性面试题03.05. 栈排序排序方案数特征识别模式操作序列包含等量的push/pop任意前缀中push次数 ≥ pop次数这与括号问题的限制条件同构Python模拟解法def validateStackSequences(pushed, popped): stack [] i 0 for num in pushed: stack.append(num) while stack and stack[-1] popped[i]: stack.pop() i 1 return not stack # 计数公式 def stackPermutations(n): return catalan(n)4. 不相交弦问题在圆周上标记2n个点用n条不相交的弦连接这些点求方案总数。这是卡特兰数的几何解释。LeetCode变形题不相交的握手会员题多边形三角剖分问题解题思路拆解固定一个点作为弦的端点将圆分成两个部分避免弦交叉递推公式f(n) Σf(i)*f(n-i-1)Python实现def chordCount(n): dp [0]*(n1) dp[0] 1 for i in range(1, n1): for j in range(i): dp[i] dp[j] * dp[i-j-1] return dp[n]5. 路径不越界问题在n×n网格中从(0,0)到(n,n)不越过对角线的路径数对应第n个卡特兰数。LeetCode代表题目不同路径基础版不同路径 II带障碍物不同路径 III进阶版卡特兰数适用条件网格必须是n×n正方形路径不允许越过主对角线每步只能向右或向上移动路径计数实现def uniquePaths(n): from math import comb return comb(2*n, n) - comb(2*n, n-1) # 动态规划版 def uniquePathsDP(n): dp [[1]*(n1) for _ in range(n1)] for i in range(1, n1): for j in range(i1, n1): dp[i][j] dp[i-1][j] dp[i][j-1] return dp[n][n]性能对比表方法n5n10n20组合公式0.01ms0.01ms0.01ms动态规划0.05ms0.21ms3.4ms实战技巧与优化策略识别卡特兰数问题的关键在于发现递归子结构。当问题满足以下特征时应考虑卡特兰数解法分治特性问题可分解为相似的子问题乘法原理整体方案数为各子问题方案数的乘积加法原理需要汇总所有可能的分割方式记忆化实现模板from functools import lru_cache lru_cache(maxsizeNone) def catalan(n): if n 1: return 1 res 0 for i in range(n): res catalan(i) * catalan(n-1-i) return res预处理卡特兰数表适合多次查询def precompute_catalan(max_n): catalan [1]*(max_n1) for i in range(2, max_n1): catalan[i] catalan[i-1]*(4*i-2)//(i1) return catalan在算法竞赛或面试中对卡特兰数问题的处理可分为三个层次初级识别问题模式直接套用公式中级实现动态规划解法理解递推关系高级改造问题使其符合卡特兰数模型