一、题目描述
给定整数：
n要求：
使用 1 ~ n 这 n 个不同节点 构造所有可能的二叉搜索树（BST）返回：
不同 BST 的数量例如：
示例 1
输入：
n = 3输出：
5对应的五种 BST：
示例 2
输入：
n = 1输出：
1二、问题本质
这道题不是让你：
构造具体树而是：
统计有多少种不同结构因此核心问题变成：
BST 的结构数量如何计算？三、二叉搜索树的关键性质
BST 满足：
左子树所有节点 < 根节点 右子树所有节点 > 根节点因此：
如果选择：
i作为根节点。
那么：
左子树： 1 ~ i-1 右子树： i+1 ~ n节点数量分别为：
左子树节点数 = i-1 右子树节点数 = n-i四、最核心的思想：分治
假设：
f(n)表示：
n 个节点能够构造的 BST 数量如果：
i 作为根节点那么：
左子树有：
f(i-1)种构造方式。
右子树有：
f(n-i)种构造方式。
由于：
左右子树相互独立根据乘法原理：
当前根节点的 BST 数量 = f(i-1) * f(n-i)枚举所有根节点：
i = 1 ~ n所以：
f(n) = Σ f(i-1) * f(n-i)即：
f(n) = f(0)*f(n-1) + f(1)*f(n-2) + ... + f(n-1)*f(0)这就是：
卡特兰递推公式五、动态规划推导
定义：
dp[i]表示：
i 个节点构成 BST 的数量状态转移方程
dp[i] += dp[j-1] * dp[i-j]其中：
j 表示根节点六、为什么是乘法？
例如：
左子树有 2 种 右子树有 3 种那么：
总方案数 = 2 × 3 = 6因为：
每一种左子树：
都能和每一种右子树：
自由组合这是经典：
组合计数思想。
七、边界条件
dp[0] 为什么是 1？
这是本题最容易疑惑的地方。
dp[0] = 1表示：
空树也算一种 BST为什么？
因为：
例如：
只有左子树 没有右子树时：
我们需要：
左子树方案数 × 空树方案数如果：
dp[0] = 0会导致：
整个结果变成 0数学上不合理。
因此：
空结构也算一种合法情况dp[1]
dp[1] = 1只有一个节点：
只能构造一种 BST八、动态规划代码实现
#include <iostream> #include <vector> using namespace std; class Solution { public: int numTrees(int n) { vector<int> dp(n + 1, 0); // 边界条件 dp[0] = 1; dp[1] = 1; // 计算 dp[i] for (int i = 2; i <= n; i++) { // 枚举根节点 for (int j = 1; j <= i; j++) { dp[i] += dp[j - 1] * dp[i - j]; } } return dp[n]; } };九、完整推导过程（n = 3）
dp[0]
1dp[1]
1dp[2]
枚举根：
根 = 1
左：
0 个节点右：
1 个节点方案：
dp[0] * dp[1] = 1 * 1 = 1根 = 2
左：
1 个节点右：
0 个节点方案：
dp[1] * dp[0] = 1 * 1 = 1因此：
dp[2] = 2dp[3]
根 = 1
dp[0] * dp[2] = 1 * 2 = 2根 = 2
dp[1] * dp[1] = 1根 = 3
dp[2] * dp[0] = 2总和：
2 + 1 + 2 = 5因此：
dp[3] = 5十、卡特兰数正式登场
你会发现：
1 1 2 5 14 42 132 ...这就是著名的：
Catalan Number（卡特兰数）十一、什么是卡特兰数？
卡特兰数是组合数学中极其经典的一类计数序列。
定义：
C0 = 1 Cn = Σ Ci * C(n-1-i)即：
Cn = C0Cn-1 + C1Cn-2 + ... + Cn-1C0与本题完全一致。
十二、卡特兰数经典问题
卡特兰数会频繁出现在：
1. 不同 BST 数量
本题。
2. 合法括号序列数量
例如：
n 对括号有多少种合法组合3. 出栈序列数量
例如：
n 个元素有多少种合法出栈顺序4. 满二叉树结构数量
5. 凸多边形三角划分
6. Dyck Path
它是算法竞赛中最经典的组合计数之一。
十三、卡特兰数通项公式
除了 DP：
还有数学公式：
C_n = \frac{1}{n+1}\binom{2n}{n}
也可以写成：
C_n = \binom{2n}{n} - \binom{2n}{n-1}
十四、为什么会出现卡特兰数？
因为 BST 的构造过程满足：
根节点划分左右区间 左右子树递归独立这种：
递归划分结构是卡特兰数最典型的特征。
十五、数学公式代码（组合数）
class Solution { public: int numTrees(int n) { long long C = 1; for (int i = 0; i < n; i++) { C = C * 2 * (2 * i + 1) / (i + 2); } return (int)C; } };十六、为什么动态规划更适合面试？
虽然公式法更快。
但是：
面试官更关注：
状态定义 递推关系 分治思想因此：
DP 解法最推荐因为它体现了：
问题拆解能力十七、复杂度分析
动态规划
状态数：
n每个状态枚举：
n时间复杂度：
O(n²)空间复杂度：
O(n)数学公式
时间复杂度：
O(n)空间复杂度：
O(1)十八、常见错误总结
错误1：dp[0] 写成 0
这是最经典错误。
正确：
dp[0] = 1因为：
空树也算一种情况错误2：左右子树写成加法
错误：
dp[i] += dp[left] + dp[right]正确：
dp[i] += dp[left] * dp[right]因为：
左右子树独立组合错误3：循环边界错误
根节点：
1 ~ i不要漏掉：
i
