vvrf / DSA.log

问题拆解

用 1 到 n 这些节点能组成多少棵结构互不相同的二叉搜索树？如果真去枚举每一棵树，形态数是指数级的，n 稍大就没法穷举。

突破口是 BST 的性质：一旦选定 i 当根，左子树必然由 1..i-1 组成，右子树必然由 i+1..n 组成，划分是唯一确定的。更关键的一步观察是：子树的形态数只和节点个数有关，与具体是哪些数无关——{1,2,3} 能摆出的 BST 形态和 {5,6,7} 一模一样。于是状态可以压缩成一维：设 G(k) 表示 k 个节点的 BST 形态数。

左子树怎么长、右子树怎么长，彼此互不干涉：左边每一种形态都能和右边每一种形态自由搭配。这就是乘法原理，也是 G(i-1) * G(n-i) 这个乘积的全部含义。

对根的位置分类，各类互不重叠又覆盖所有情况，所以求和：

G(n) = Σ G(i-1) * G(n-i)，i 从 1 取到 n

这个递推式在数学上就是卡特兰数。

枚举根节点的递推

按 G 的定义从小规模往大规模填表即可。唯一要想清楚的边界是 G(0) = 1：空树也算一种形态，否则只要某一侧子树为空，乘积就被清零了。

public int numTrees(int n) {
    int[] g = new int[n + 1];
    g[0] = 1; // 空树也是一种形态
    for (int i = 1; i <= n; i++) {
        for (int root = 1; root <= i; root++) {
            g[i] += g[root - 1] * g[i - root]; // 左子树形态数 × 右子树形态数
        }
    }
    return g[n];
}

def numTrees(n: int) -> int:
    g = [0] * (n + 1)
    g[0] = 1  # 空树也是一种形态
    for i in range(1, n + 1):
        for root in range(1, i + 1):
            g[i] += g[root - 1] * g[i - root]  # 左子树形态数 × 右子树形态数
    return g[n]

func numTrees(n int) int {
    g := make([]int, n+1)
    g[0] = 1 // 空树也是一种形态
    for i := 1; i <= n; i++ {
        for root := 1; root <= i; root++ {
            g[i] += g[root-1] * g[i-root] // 左子树形态数 × 右子树形态数
        }
    }
    return g[n]
}

pub fn num_trees(n: i32) -> i32 {
    let n = n as usize;
    let mut g = vec![0i64; n + 1];
    g[0] = 1; // 空树也是一种形态
    for i in 1..=n {
        for root in 1..=i {
            g[i] += g[root - 1] * g[i - root]; // 左子树形态数 × 右子树形态数
        }
    }
    g[n] as i32
}

内层循环枚举“谁当根”：根左边有 root - 1 个节点，右边有 i - root 个，两侧形态数相乘后累加。注意这里加的是乘积而不是和——初学者容易写成 g[root-1] + g[i-root]，那算的是“左右子树形态数之和”，丢掉了搭配关系。另外题目虽然保证 n <= 19、结果不溢出 int，Rust 版仍用 i64 中转一下，省去对边界的心算。

复杂度

指标	复杂度	原因
时间	`O(n²)`	每个规模 `i` 要枚举 `i` 种根的位置
空间	`O(n)`	一张一维的 `G` 表

可以迁移的模式

计数 DP 先找一个“互不重叠、覆盖全部”的分类维度，这里是“谁当根”；
两个互相独立的子结构，方案数用乘法原理相乘，再对分类求和；
当子问题的答案只依赖规模、不依赖具体元素时，状态就能从“集合”压缩成“个数”。

“枚举根、左右相乘、按根求和”这套动作还会出现在第 95 题（要求真正构造出所有树）以及一切卡特兰数结构里——括号匹配、出栈序列，本质都是同一条递推。