不同的二叉搜索树

题目

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

示例1:
输入：n = 3
输出：5
示例 2：
输入：n = 1
输出：1

提示： 1 <= n <= 19 二叉搜索树定义：（又名：二叉查找树，有序二叉树，排序二叉树）

1. 该树左子树上所有节点的数值都比根节点小。
2. 该树右子树上所有节点的数值都比根节点大。
3. 该树任意的左、右子树也分别为二叉搜索树。

思路：

动态规划，原问题可以分解为规模较小的子问题，子问题的解可以重用解决方案。

分析： 给了一个从 1 到 n 的数组，为了得到可以构建几颗二叉搜索树，可以遍历从 1 到 n 每个元素，分别将每个元素作为根节点，将 1 至 (i - 1) 的元素作为左子树，将 (i + 1) 至 n 的元素作为右子树。

• 对于左子树：可以用同样的思路，获取左子树中 1 至 (i - 1) 中有几种二叉搜索树 m
• 对于右子树：可以获取从 (i + 1) 到 n 有几种二叉搜索树 n 即表示：以 n 为根节点，可以构建 m * n 个不同的二叉搜索树。

根据上面的思路，给定一个从 1 到 n 的数组，要得到能构建的所有二叉搜索树的总数， 那就遍历该数组，分别让每个元素都作为根节点，分别求出所有的数量，最后相加即为结果。

假设有两个函数：

• G(n): 长度为 n 的序列，能构成的不同二叉搜索树的个数。
• F(i, n): 以 i (1 < i < n)为根节点，长度为 n ，能构成的不同二叉搜索树的个数。

3. 所以可以得到：

   • G(n) = F(1, n) + F(2, n) + F(3, n) + ... + F(n, n)
   • F(i, n) = G(i - 1) * G(n - i)

4. 边界情况：

   • G(0) = 1
   • G(1) = 1

代码

const numTrees = (n) => {
    const arr = new Array(n + 1).fill(0);
    arr[0] = 1;
    arr[1] = 1;
    for (let i = 2; i <= n; i++) {
            for (let j = 1; j <= i; j++) {
                arr[i] = arr[i] + arr[j - 1] * arr[i - j]
            }
        }
    return arr[n]
}