每日OJ题_其它背包问题④_力扣96. 不同的二叉搜索树（卡特兰数）

目录

力扣96. 不同的二叉搜索树

解析代码

---

力扣96. 不同的二叉搜索树

96. 不同的二叉搜索树

难度 中等

给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种？返回满足题意的二叉搜索树的种数。

示例 1：

输入：n = 3
输出：5

示例 2：

输入：n = 1
输出：1

提示：

• 1 <= n <= 19

class Solution {
public:
    int numTrees(int n) {
 
    }
};

---

解析代码

        这道题属于卡特兰数的一个应用，同样能解决的问题还有合法的进出栈序列、括号匹配的括号序列、电影购票等等。如果感兴趣的可以继续百度搜索卡特兰数，会有很多详细的介绍。

        这道题的状态表示就是根据拆分出相同子问题的方式，抽象出来一个状态表示： 当在求个数为 n 的 BST（二叉搜索树） 的个数的时候，当确定一个根节点之后，左右子树的结点个数也确定了。此时左右子树就会变成相同的子问题，因此可以这样定义状态表示： dp[i] 表示：当结点的数量为 i 个的时候，一共有多少颗 BST 。 难的是如何推导状态转移方程，因为它跟之前常见的状态转移方程不是很像。

状态转移方程：

        对于 dp[i] ，此时我们已经有 i 个结点了，为了方便叙述，将这 i 个结点排好序，并且编上 1、2、3、4、5.....i 的编号。那么对于所有不同的 BST ，可以按照下面的划分规则，分成不同的 i 类：按照不同的头结点来分类。分类结果就是：

1. 头结点为 1 号结点的所有 BST
2. 头结点为 2 号结点的所有 BST
3. ......

如果能求出每一类中的 BST 的数量，将所有类的 BST 数量累加在一起，就是最后结果。

        接下来选择头结点为 j 号的结点，来分析这 i 类 BST 的通用求法。如果选择 j 号结点来作为头结点，根据 BST 的定义：

• j 号结点的左子树的结点编号应该在 [1, j - 1] 之间，一共有 j - 1 个结点。那么 j 号结点作为头结点的话，它的左子树的种类就有 dp[j - 1] 种（回顾此 dp 数组的定义）。
• j 号结点的右子树的结点编号应该在 [j + 1, i] 之间，一共有 i - j 个结点。那么 j 号结点作为头结点的话，它的右子树的种类就有 dp[i - j] 种。

        根据排列组合的原理可得： j 号结点作为头结点的 BST 的种类一共有 dp[j - 1] *dp[i - j] 种。因此只要把不同头结点的 BST 数量累加在⼀起，就能得到 dp[i] 的值： dp[i] += dp[j - 1] * dp[i - j] ( 1 <= j <= i) （这个公式就是卡特兰数的递推公式）。注意用的是 += ，并且 j 从 1 变化到 i 。

初始化： 注意到每一个状态转移里面的 j - 1 和 i - j 都是小于 i 的，并且可能会用到前一个的状态（当 i = 1，j = 1 的时候，要用到 dp[0] 的数据）。因此要先把第一个元素初始化。 当 i = 0 的时候，表示一颗空树，空树也是一颗二叉搜索树，因此 dp[0] = 1 。

填表顺序： 根据状态转移方程易得从左往右。

返回值： 根据状态表示，返回 dp[n]。

class Solution {
public:
    int numTrees(int n) {
        vector<int> dp(n + 1, 0);
        // dp[i] 表示：当结点的数量为 i 个的时候，一共有多少颗 BST 
        dp[0] = 1; // 空树也是二叉搜索树
        for(int i = 1; i <= n; ++i) // 枚举结点个数
        {
            for(int j = 1; j <= i; ++j) // 枚举每⼀个根节点
            {
                dp[i] += dp[j - 1] * dp[i - j];
            }
        }
        return dp[n];
    }
};