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

示例 1：

输入：n = 3
输出：5

示例 2：
输入：n = 1
输出：1

提示：
1 <= n <= 19

思路

给定一个有序序列 1⋯n，为了构建出一棵二叉搜索树，我们可以遍历每个数字 i，将该数字作为树根，将 1⋯(i−1) 序列作为左子树，将 (i+1)⋯n 序列作为右子树。接着我们可以按照同样的方式递归构建左子树和右子树。

在上述构建的过程中，由于根的值不同，因此我们能保证每棵二叉搜索树是唯一的。

由此可见，原问题可以分解成规模较小的两个子问题，且子问题的解可以复用。因此，我们可以想到使用动态规划来求解本题。动态规划介绍点这里

假设 n 个节点存在二叉排序树的个数是 G (n)，令 f(i) 为以 i 为根的二叉搜索树的个数，则
G(n)=f(1)+f(2)+f(3)+f(4)+…+f(n)

当 i 为根节点时，其左子树节点个数为 i-1 个，右子树节点为 n-i，则
f(i)=G(i−1)∗G(n−i)

综合两个公式可以得到公式
G(n)=G(0)∗G(n−1)+G(1)∗(n−2)+…+G(n−1)∗G(0)

int numTrees(int n) {
    int G[n+1];
    memset(G, 0, sizeof(G));
    G[0] = G[1] = 1;
    
    for(int i = 2; i < n+1; i++){
        for(int j = 1; j <i+1; j++){
            G[i] +=G[j-1]*G[i-j]; 
        }
    }

复杂度分析

时间复杂度 : O(n2)，其中 n 表示二叉搜索树的节点个数。G(n) 函数一共有 n 个值需要求解，每次求解需要 O(n) 的时间复杂度，因此总时间复杂度为 O(n2)。

空间复杂度 : O(n)。我们需要 O(n) 的空间存储 G 数组。

另辟蹊径

这个时候就有人会说了，主播主播，这个解法还是太费脑子了，复杂度还高，有没有更加简单又强势的解法推荐？有的兄弟有的。我们注意到

1 <= n <= 19

于是乎，我们拿起计算器进行一点小小的运算，便可以得到下面的解法

int numTrees(int n) {
    switch(n) 
        case 1: return 1;
        case 2: return 2;
        case 3: return 5;
        case 4: return 14;
        case 5: return 42;
        case 6: return 132;
        case 7: return 429;
        case 8: return 1430;
        case 9: return 4862;
        case 10: return 16796;
        case 11: return 58786;
        case 12: return 208012;
        case 13: return 742900;
        case 14: return 2674440;
        case 15: return 9694845;
        case 16: return 35357670;
        case 17: return 129644790;
        case 18: return 477638700;
        case 19: return 1767263190;
        default: return 0;
    }
}

时间复杂度和空间复杂度都是O(1)的顶级算法，最重要的是人人都能看懂！！！这才是真正的算法！！！