题目链接：96. 不同的二叉搜索树

题解：

本题就是求卡特兰数，这里使用动态规划来写！

题目简述：

求n个节点可以构成二叉搜索树的个数！

题解：

可以直接利用卡特兰数公式来求，似乎不太好求！

这里使用动态规划来求：

和上一道类似，同样是乘法原理，j表示长度为1 ~ i的根节点的位置，左子树的长度为 j - 1，右子树的长度为i - j

状态表示：f[i]表示i长度的二叉搜索树个数

状态计算： f[i] += f[j - 1] * f[i - j]（j可以取该区间任何位置，累加关系） 乘法原理，左边乘以右边

初始转态： f[0] = 1，同样这个初始状态由能否使得所有状态算对即可！当i, j都为1时，f[i] = f[j - 1] * f[i - j] 应该为1，即f[0] = 1

最终答案： f[n] 即n长度的二叉搜索树个数

注意：对于1 ~ 5 和2 ~ 6可以构成的二叉搜索树是一样的，可以这样想，将1 ~ 5构成的二叉搜索树根据对应关系可以全部替换为2 ~ 6，即二叉搜索树的个数时有区间长度决定的！

时间复杂度：O(n^2)

AC代码：

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    int numTrees(int n) {
        vector<int> f(n + 1);
        f[0] = 1;
        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= i; j++)
                f[i] += f[j - 1] * f[i - j];
        return f[n];
    }
};