题目描述
思路解析
一句话答案：LeetCode 96 不同的二叉搜索树用动态规划求解：dp[i] 表示 i 个节点能组成的二叉搜索树种数，枚举每个数当根，左子树方案数乘右子树方案数，再把所有根的结果加起来，即 dp[i] = Σ dp[j] × dp[i-1-j]。这串数正是卡特兰数，n=8 时答案 1430。时间 O(n²)、空间 O(n)。
这道题数的是什么，为什么只看形状
题目给整数 n，节点值固定是 1 到 n，问能组成多少种结构不同的二叉搜索树（BST，左子树全小于根、右子树全大于根的二叉树）。听起来要同时考虑「放哪些值」和「长什么形状」，其实只需要数形状。原因藏在 BST 的一条性质里：它的中序遍历必然是升序，也就是恒为 1 到 n。这意味着给定一种树的形状，把 1 到 n 按中序位置填进去的方式是唯一的——形状定了，每个节点放谁就定了。所以答案只跟节点个数有关，跟具体取哪些值无关。
为什么想到枚举根来分解问题
直接枚举所有树形是不现实的，树形数量增长极快。突破口是 BST 的结构约束：一旦选定某个数 k 当根，比 k 小的数必须全部进左子树、比 k 大的数必须全部进右子树，两边各是多少个节点就完全确定了。整棵树的问题被根一刀切成两个更小的同类问题。
更关键的是，由上一节的结论，子树的方案数只取决于节点个数。左边有 j 个节点，不管这 j 个具体是哪些值，能搭出的形状数都一样。于是「n 个节点的 BST 数」可以由「更少节点的 BST 数」推出来——这正是动态规划要的递推结构。
dp 怎么定义，为什么左右方案数是相乘
定义 dp[i] 为 i 个节点能组成的结构不同的 BST 个数。计算 dp[i] 时枚举根：让第 k 个数当根，左子树分到 j = k-1 个节点、右子树分到 i-1-j 个。左子树有 dp[j] 种搭法，右子树有 dp[i-1-j] 种，左右两边互不干扰、可以自由组合，按乘法原理这一种根贡献 dp[j] × dp[i-1-j] 种树。
不同的根产生的树根节点不同，绝不会重复，按加法原理把 i 种根的贡献全部加起来，就是 dp[i] = Σ dp[j] × dp[i-1-j]，j 从 0 取到 i-1。这里最容易犯的错是把左右子树的方案数加起来——加法数的是「二选一」，而左右子树是同时存在、独立各选一种，必须相乘。
dp[0] 为什么必须等于 1 而不是 0
空树也算一种合法形态：根没有左孩子时，左子树就是空树，这种情况实实在在贡献着方案。dp[0] 在递推式里始终以乘数身份出现，比如最小的数当根时贡献是 dp[0] × dp[i-1]，若 dp[0] 设成 0，所有单边为空的树会被整体乘没，dp[1] 都算不出来。把 dp[0] 定为 1，读作「空树恰有一种形态」，整个递推才立得住。
从 dp[0]=1、dp[1]=1 出发依次递推，得到 2、5、14、42、132、429、1430……n=8 时答案就是 1430。
复杂度多少，和卡特兰数是什么关系
时间复杂度 O(n²)：外层 i 从 1 递推到 n，内层枚举 i 个根。空间 O(n)，一维 dp 数组。
dp[i] = Σ dp[j] × dp[i-1-j] 正是卡特兰数的递推式，所以 dp[n] 就是第 n 个卡特兰数，有封闭公式 C(2n,n)/(n+1)。合法括号序列、出栈顺序等经典计数问题与本题同构，面试里能点出这一层，说明你看到的不只是一道题，而是一类「枚举分割点、左右相乘再求和」的计数结构。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
核心一句话：枚举根，左子树 j 个节点、右子树 i-1-j 个，方案数相乘再把所有根加起来。
上行是节点数 n（固定参照），下行 dp 待填。先定基准：0 个节点是「空树」，只有 1 种，dp[0]=1。
空树（一个节点都没有）也是一种合法形状，dp[0]=1。它是后面所有相乘的「乘 1」基底。
算 dp[1]：让第 1 个数当根 —— 它左边 0 个节点有 dp[0]=1 种、右边 0 个有 dp[0]=1 种，左右独立相乘 = 1。累加到这里共 1。
把 1 个根全枚举完，方案数加起来 = 1，填进 dp[1]。
算 dp[2]：让第 1 个数当根 —— 它左边 0 个节点有 dp[0]=1 种、右边 1 个有 dp[1]=1 种，左右独立相乘 = 1。累加到这里共 1。
算 dp[2]：让第 2 个数当根 —— 它左边 1 个节点有 dp[1]=1 种、右边 0 个有 dp[0]=1 种，左右独立相乘 = 1。累加到这里共 2。
把 2 个根全枚举完，方案数加起来 = 2，填进 dp[2]。
算 dp[3]：让第 1 个数当根 —— 它左边 0 个节点有 dp[0]=1 种、右边 2 个有 dp[2]=2 种，左右独立相乘 = 2。累加到这里共 2。
算 dp[3]：让第 2 个数当根 —— 它左边 1 个节点有 dp[1]=1 种、右边 1 个有 dp[1]=1 种，左右独立相乘 = 1。累加到这里共 3。
算 dp[3]：让第 3 个数当根 —— 它左边 2 个节点有 dp[2]=2 种、右边 0 个有 dp[0]=1 种，左右独立相乘 = 2。累加到这里共 5。
把 3 个根全枚举完，方案数加起来 = 5，填进 dp[3]。
算 dp[4]：让第 1 个数当根 —— 它左边 0 个节点有 dp[0]=1 种、右边 3 个有 dp[3]=5 种，左右独立相乘 = 5。累加到这里共 5。
算 dp[4]：让第 2 个数当根 —— 它左边 1 个节点有 dp[1]=1 种、右边 2 个有 dp[2]=2 种，左右独立相乘 = 2。累加到这里共 7。
算 dp[4]：让第 3 个数当根 —— 它左边 2 个节点有 dp[2]=2 种、右边 1 个有 dp[1]=1 种，左右独立相乘 = 2。累加到这里共 9。
算 dp[4]：让第 4 个数当根 —— 它左边 3 个节点有 dp[3]=5 种、右边 0 个有 dp[0]=1 种，左右独立相乘 = 5。累加到这里共 14。
把 4 个根全枚举完，方案数加起来 = 14，填进 dp[4]。
算 dp[5]：让第 1 个数当根 —— 它左边 0 个节点有 dp[0]=1 种、右边 4 个有 dp[4]=14 种，左右独立相乘 = 14。累加到这里共 14。
算 dp[5]：让第 2 个数当根 —— 它左边 1 个节点有 dp[1]=1 种、右边 3 个有 dp[3]=5 种，左右独立相乘 = 5。累加到这里共 19。
算 dp[5]：让第 3 个数当根 —— 它左边 2 个节点有 dp[2]=2 种、右边 2 个有 dp[2]=2 种，左右独立相乘 = 4。累加到这里共 23。
算 dp[5]：让第 4 个数当根 —— 它左边 3 个节点有 dp[3]=5 种、右边 1 个有 dp[1]=1 种，左右独立相乘 = 5。累加到这里共 28。
算 dp[5]：让第 5 个数当根 —— 它左边 4 个节点有 dp[4]=14 种、右边 0 个有 dp[0]=1 种，左右独立相乘 = 14。累加到这里共 42。
把 5 个根全枚举完，方案数加起来 = 42，填进 dp[5]。
算 dp[6]：让第 1 个数当根 —— 它左边 0 个节点有 dp[0]=1 种、右边 5 个有 dp[5]=42 种，左右独立相乘 = 42。累加到这里共 42。
算 dp[6]：让第 2 个数当根 —— 它左边 1 个节点有 dp[1]=1 种、右边 4 个有 dp[4]=14 种，左右独立相乘 = 14。累加到这里共 56。
算 dp[6]：让第 3 个数当根 —— 它左边 2 个节点有 dp[2]=2 种、右边 3 个有 dp[3]=5 种，左右独立相乘 = 10。累加到这里共 66。
算 dp[6]：让第 4 个数当根 —— 它左边 3 个节点有 dp[3]=5 种、右边 2 个有 dp[2]=2 种，左右独立相乘 = 10。累加到这里共 76。
算 dp[6]：让第 5 个数当根 —— 它左边 4 个节点有 dp[4]=14 种、右边 1 个有 dp[1]=1 种，左右独立相乘 = 14。累加到这里共 90。
算 dp[6]：让第 6 个数当根 —— 它左边 5 个节点有 dp[5]=42 种、右边 0 个有 dp[0]=1 种，左右独立相乘 = 42。累加到这里共 132。
把 6 个根全枚举完，方案数加起来 = 132，填进 dp[6]。
算 dp[7]：让第 1 个数当根 —— 它左边 0 个节点有 dp[0]=1 种、右边 6 个有 dp[6]=132 种，左右独立相乘 = 132。累加到这里共 132。
算 dp[7]：让第 2 个数当根 —— 它左边 1 个节点有 dp[1]=1 种、右边 5 个有 dp[5]=42 种，左右独立相乘 = 42。累加到这里共 174。
算 dp[7]：让第 3 个数当根 —— 它左边 2 个节点有 dp[2]=2 种、右边 4 个有 dp[4]=14 种，左右独立相乘 = 28。累加到这里共 202。
算 dp[7]：让第 4 个数当根 —— 它左边 3 个节点有 dp[3]=5 种、右边 3 个有 dp[3]=5 种，左右独立相乘 = 25。累加到这里共 227。
算 dp[7]：让第 5 个数当根 —— 它左边 4 个节点有 dp[4]=14 种、右边 2 个有 dp[2]=2 种，左右独立相乘 = 28。累加到这里共 255。
算 dp[7]：让第 6 个数当根 —— 它左边 5 个节点有 dp[5]=42 种、右边 1 个有 dp[1]=1 种，左右独立相乘 = 42。累加到这里共 297。
算 dp[7]：让第 7 个数当根 —— 它左边 6 个节点有 dp[6]=132 种、右边 0 个有 dp[0]=1 种，左右独立相乘 = 132。累加到这里共 429。
把 7 个根全枚举完，方案数加起来 = 429，填进 dp[7]。
算 dp[8]：让第 1 个数当根 —— 它左边 0 个节点有 dp[0]=1 种、右边 7 个有 dp[7]=429 种，左右独立相乘 = 429。累加到这里共 429。
算 dp[8]：让第 2 个数当根 —— 它左边 1 个节点有 dp[1]=1 种、右边 6 个有 dp[6]=132 种，左右独立相乘 = 132。累加到这里共 561。
算 dp[8]：让第 3 个数当根 —— 它左边 2 个节点有 dp[2]=2 种、右边 5 个有 dp[5]=42 种，左右独立相乘 = 84。累加到这里共 645。
算 dp[8]：让第 4 个数当根 —— 它左边 3 个节点有 dp[3]=5 种、右边 4 个有 dp[4]=14 种，左右独立相乘 = 70。累加到这里共 715。
算 dp[8]：让第 5 个数当根 —— 它左边 4 个节点有 dp[4]=14 种、右边 3 个有 dp[3]=5 种，左右独立相乘 = 70。累加到这里共 785。
算 dp[8]：让第 6 个数当根 —— 它左边 5 个节点有 dp[5]=42 种、右边 2 个有 dp[2]=2 种，左右独立相乘 = 84。累加到这里共 869。
算 dp[8]：让第 7 个数当根 —— 它左边 6 个节点有 dp[6]=132 种、右边 1 个有 dp[1]=1 种，左右独立相乘 = 132。累加到这里共 1001。
算 dp[8]：让第 8 个数当根 —— 它左边 7 个节点有 dp[7]=429 种、右边 0 个有 dp[0]=1 种，左右独立相乘 = 429。累加到这里共 1430。
把 8 个根全枚举完，方案数加起来 = 1430，填进 dp[8]。
最右 dp[8]=1430 就是 8 个节点能搭出的不同 BST 个数（这串 1,1,2,5,14,42,132,429,1430 就是卡特兰数）。
小 n 边界先想清，是后面递推的基底。
两个高频追问。
参考代码
def numTrees(n): dp = [0] * (n + 1) dp[0] = 1 for i in range(1, n + 1): for j in range(i): # 左子树节点数 dp[i] += dp[j] * dp[i - 1 - j] return dp[n]复杂度
- 时间：O(n²)，每个 i 枚举 i 个根
- 空间：O(n)，一维 dp 数组
易错点
面试追问把动画讲成自己的话
追问为什么这串数是卡特兰数？
追问为什么节点值不影响个数？
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。再去主线里挑下一道练手。
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题