【Day 68 】2022-02-17 - 96. 不同的二叉搜索树

[azl397985856]

96. 不同的二叉搜索树

入选理由

暂无

题目地址

https://leetcode-cn.com/problems/unique-binary-search-trees/

前置知识

• 二叉搜索树
• 分治

  题目描述

  
  给定一个整数 n，求以 1 ... n 为节点组成的二叉搜索树有多少种？

示例:

输入: 3 输出: 5 解释: 给定 n = 3, 一共有 5 种不同结构的二叉搜索树:

1 3 3 2 1 \ / / / \ \ 3 2 1 1 3 2 / / \ \ 2 1 2 3

[Richard-LYF]

class Solution: def numTrees(self, n: int) -> int:

    dp = [0] *(n+1)
    dp[0] = 1

    for i in range(1,n+1):
        for j in range(i):
            dp[i] += dp[j]*dp[i-1-j]

    return dp[-1]

on2 on

[yetfan]

思路 n个节点，要以每个点为根计算一次数量最后求和 以 i 为根，即求 i-1 个左边节点计算 + n-i 个右边节点计算 dp[i] += dp[j-1] * dp[i-j]

代码

class Solution:
    def numTrees(self, n: int) -> int:
        dp = [1, 1] + [0] * (n-1)

        for i in range(2, n+1):
            for j in range(1, i+1):
                dp[i] += dp[j-1] * dp[i-j]
        return dp[n]

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

[ZJP1483469269]

class Solution:
    def numTrees(self, n: int) -> int:
        g = [0] * (n + 1)
        g[0] , g[1] = 1 , 1
        for i in range(2 , n+1):
            for j in range(1 , i + 1):
                g[i] += g[j - 1] * g[i - j] 

        return g[n]

[hulichao]

思路

以每个节点为根进行计算，然后求和 dp[i] += dp[j-1] + dp[i-j];

代码

class Solution {
    // 思路，以每个节点为根进行计算，然后求和
    // dp[i] += dp[j-1] + dp[i-j]; 
    public int numTrees(int n) {
        int[] dp = new int[n + 1];
        dp[0] = 1;
        dp[1] = 1;
        for(int i = 2; i <= n; i++) {
            for (int j = 1; j <= i; j++) {
                dp[i] += dp[j - 1] * dp[i - j];
            }
        }

        return dp[n];
    }
}

复杂度分析

• 时间复杂度：O(N^2)，其中 N 为数组长度。
• 空间复杂度：O(1)

[ZacheryCao]

Idea:

Divide and Conquer: Let's say it has a BST with N nodes. For the root at different BSTs, it has two subtrees. One left, one right. Each subtree has 0<=K=N-1 nodes. The amount of BST with 0<=K=N-1nodes has already been verified in previous steps. Let's say for K nodes tree, it has T(K) BSTs. Then, for the amount of BST with ith node as the root, it has T(i-1) *T(N-i) BSTs. In order to get the total BSTs for N nodes, we just need to sum the amount of BSTs with 1~N th node as the root.

Code:

class Solution {
public:
    int numTrees(int n) {
        if(n<2) return n;
        vector<int> dp(n+1);
        dp[0] = 1;
        dp[1] = 1;
        dp[2] = 2;
        for(int i = 3; i<= n; i++){
            for(int j = 1; j<=i; j++){
                dp[i] += dp[i-j]*dp[j-1];
            }
        }
        return dp.back();
    }
};

Complexity:

Time: O(N^2) Space: O(N)

[moirobinzhang]

Code:

public class Solution { public int NumTrees(int n) { int[] dp = new int[n + 1]; dp[0] = 1; dp[1] = 1;

    for (int i = 2; i <= n; i++)
    {
        for (int j = 1; j <= i; j++)
            dp[i] += dp[j - 1] * dp[i - j];
    }

    return dp[n];
}

}

[zhangzz2015]

思路

• 使用dp 方法， dp[n] 我们可以loop i 从 1 到 n 作为 root。那么i-1 作为root的左子树，n-i 作为root的右子树，因此dp[n] = sum_i_n dp[i-1]*dp[n-i] 时间复杂度位O(n^2)，空间复杂度位O(n)

关键点

代码

• 语言支持：C++

C++ Code:

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

        ///  dp[n] ------>     loop i from 1 to n.  dp[i-1] * dp[n-i] 
        //  dp[1]        1
        //  dp[2]   dp[0] * dp[2-1] + dp[2-1] * dp[0]  = 2 
        //  dp[3]   dp[0] * dp[3-1] + dp[1] * dp[3-2] + dp[2] * dp[3-3]
        //                2   +  1  +  2 

        vector<int> dp(n+1,0);
        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];         
    }
};

[zhy3213]

思路

何苦dp

代码

    @cache
    def numTrees(self, n: int) -> int:
        if n<2:
            return 1
        res=0
        for i in range(n):
            res+=self.numTrees(i)*self.numTrees(n-i-1)
        return res

[zwx0641]

class Solution { int[][] memo; public int numTrees(int n) { memo = new int[n + 1][n + 1]; return count(1, n); } int count(int lo, int hi) { if (lo > hi) return 1; if (memo[lo][hi] != 0) return memo[lo][hi]; int res = 0; for (int i = lo; i <= hi; i++) { int left = count(lo, i - 1); int right = count(i + 1, hi); res += left * right; } memo[lo][hi] = res; return res; } }

[LinnSky]

代码

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

[Tesla-1i]

class Solution:
    def numTrees(self, n: int) -> int:
        dp = [1, 1] + [0] * (n-1)

        for i in range(2, n+1):
            for j in range(1, i+1):
                dp[i] += dp[j-1] * dp[i-j]
        return dp[n]

[yan0327]

func numTrees(n int) int {
    dp := make([]int,n+1)
    dp[0] = 1
    dp[1] = 1
    for i:=2;i<=n;i++{
        for j:=0;j<i;j++{
            dp[i] += dp[j]*dp[i-1-j]
        }
    }
    return dp[n]
}

[Aobasyp]

思路 记忆化递归 class Solution { vector visited; int dp(int n) { if (visited[n]) return visited[n]; int ans = 0; for (int i = 0; i < n; ++i) ans += dp(i) * dp(n - i - 1); return visited[n] = ans; } public: int numTrees(int n) { visited.assign(n + 1, 0); visited[0] = 1; return dp(n); } };

时间复杂度是 O(N^2) 空间复杂度： O(N)

[JudyZhou95]

代码

class Solution: def numTrees(self, n: int) -> int: if n <= 1: return 1

    dp = [1, 1]

    for i in range(2, n+1):
        tmp = 0

        for j in range(i):
            tmp += dp[j] * dp[i-j-1]

        dp.append(tmp)

    return tmp

""" class Solution: visited = {0:1, 1:1}

def numTrees(self, n: int) -> int:
    if n in self.visited:
        return self.visited[n]

    res = 0
    for i in range(1, n+1):           
        res += self.numTrees(i-1) * self.numTrees(n-i)
    self.visited[n] = res

    return res

"""

[1149004121]

96. 不同的二叉搜索树

思路

分而治之。遍历[1, n],分别以其为根节点遍历树。

代码

var numTrees = function(n) {
    let map = new Map();
    return divideAndConquer(n);

    function divideAndConquer(x){
        if(map.has(x)) return map.get(x);
        if(x <= 1) return 1;
        let res = 0;
        for(let i = 1; i <= x; i++){
            res += divideAndConquer(i - 1) * divideAndConquer(x - i);
        };
        map.set(x, res);
        return res;
    }
};

复杂度分析

• 时间复杂度：O(N^2)。
• 空间复杂度：O(N)。

[FlorenceLLL]

class Solution {
    public int numTrees(int n) {

        int[] dp = new int[n+1];

        dp[0] = 1;
        dp[1] = 1;

        for(int i = 2; i <= n; i++) {
            for(int j = 0; j< i; j++) {
                dp[i] += dp[j] * dp[i-j-1]; 
            }
        }

        return dp[n];   
    }
}

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

[KennethAlgol]

class Solution {
    public int numTrees(int n) {

    int[] res = new int[n + 1];
    res[0] = 1;
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < i; j++) {
            res[i] = res[i] + res[j] * res[i - j - 1];
        }
    }
    return res[n];
    }
}

[CoreJa]

思路

• DFS记忆化：深搜最好想，考虑递归函数入参为x，x小于等于1就直接返回1，其它情况循环i从1到n，递归调用dfs(i-1)*dfs(x-i)，累加并返回。要注意需要记忆化递归，否则铁定TLE，复杂度$O(n)$
• DP：设dp[i]为所求答案，则$dp[i]=\sum_{0\leq j<i} dp[j]*dp[i-j-1]$。思路是类似的，复杂度$O(n)$
• 数学法：这个东西叫卡塔兰数，递推公式为：$C{n+1}=\sum{i=0}^nCiC{n-i}$，也可以表示为$C_{n+1}=\frac{2(2n+1)}{n+2}C_n$。前者和dp的状态转移方程一致。复杂度$O(n)$

代码

class Solution:
    # DFS记忆化：深搜最好想，考虑递归函数入参为`x`，`x`小于等于1就直接返回1，其它情况循环`i`从1到`n`，递归调用
    # `dfs(i-1)`*`dfs(x-i)`，累加并返回。要注意需要记忆化递归，否则铁定TLE，复杂度$O(n)$
    def numTrees1(self, n: int) -> int:
        @cache
        def dfs(x):
            if x <= 1:
                return 1
            return sum([dfs(i - 1) * dfs(x - i) for i in range(1, x + 1)])

        return dfs(n)

    # DP：设`dp[i]`为所求答案，则$dp[i]=\sum_{0\leq j<i} dp[j]*dp[i-j-1]$。思路是类似的，复杂度$O(n)$
    def numTrees2(self, n: int) -> int:
        dp = [1] + [0] * n
        for i in range(1, n + 1):
            for j in range(i):
                dp[i] += dp[j] * dp[i - 1 - j]
        return dp[n]

    # 数学法：这个东西叫卡塔兰数，递推公式为：$C_{n+1}=\sum_{i=0}^nC_iC_{n-i}$，也可以表示为
    # $C_{n+1}=\frac{2(2n+1)}{n+2}C_n$。前者和dp的状态转移方程一致。复杂度$O(n)$
    def numTrees(self, n: int) -> int:
        ans = 1
        for i in range(n):
            ans = ans * 2 * (2 * i + 1) // (i + 2)
        return ans

[wenlong201807]

代码块

var numTrees = function (n) {
  // 备忘录的值初始化为 0
  let memo = new Array(n + 1).fill(0).map(() => new Array(n + 1).fill(0));
  let count = (lo, hi) => {
    // base case，显然当lo > hi闭区间[lo, hi]肯定是个空区间，也就对应着空节点 null，
    // 虽然是空节点，但是也是一种情况，所以要返回 1 而不能返回 0
    if (lo > hi) return 1;
    if (memo[lo][hi] != 0) return memo[lo][hi];
    let res = 0;
    for (let i = lo; i <= hi; i++) {
      // i 的值作为根节点 root
      let left = count(lo, i - 1);
      let right = count(i + 1, hi);
      // 左右子树的组合数乘积是 BST 的总数
      res += left * right;
    }
    memo[lo][hi] = res;
    return res;
  };
  // 计算闭区间 [1, n] 组成的 BST 个数
  return count(1, n);
};

时间复杂度和空间复杂度

• 时间复杂度 O(n)
• 空间复杂度 O(1)

[charlestang]

思路

递归 + 记忆化

对于一个数列 a1，a2，……， an

选择任意 ai 作为根节点，小于 ai 的数字构成的左子树的种数，乘以大于 ai 的数字构成的右子树的种数，就以 ai 为根节点的所有 BST 种数。

每个节点都可以作为根节点，所以遍历计算后求和就可以。

代码

class Solution:
    def numTrees(self, n: int) -> int:
        @cache
        def count(l: int, r: int) -> int:
            if l >= r: return 1
            ans = 0
            for i in range(l, r + 1):
                ans += count(l, i - 1) * count(i + 1, r)
            return ans
        return count(1, n)

时间复杂度 每一层递归，里面有 n 重循环，其中一个节点做了根节点，下一层，循环总规模减少了 1，所以，最后总时间复杂度达到 O(n!)，如果不加缓存，会 TLE。

空间复杂度 O(n)

[haixiaolu]

思路

DP

代码/python

class Solution:
    def numTrees(self, n:int) -> int:
        numTree = [1] * (n + 1)

        # 0 nodes = 1 tree
        # 1 nodes = 1 tree
        for nodes in range(2, n + 1):
            total = 0
            for root in range(1, nodes + 1):
                left = root - 1
                right = nodes - root # nodes is total input 
                total += numTree[left] * numTree[right]
            numTree[nodes] = total
        return numTree[n]

• Time: O(n^2)
• Space: O(n)

[Moin-Jer]

class Solution { public int numTrees(int n) { int[] G = new int[n + 1]; G[0] = 1; G[1] = 1;

    for (int i = 2; i <= n; ++i) {
        for (int j = 1; j <= i; ++j) {
            G[i] += G[j - 1] * G[i - j];
        }
    }
    return G[n];
}

}

[alongchong]

class Solution {
    public int numTrees(int n) {
        int[] G = new int[n + 1];
        G[0] = 1;
        G[1] = 1;

        for (int i = 2; i <= n; ++i) {
            for (int j = 1; j <= i; ++j) {
                G[i] += G[j - 1] * G[i - j];
            }
        }
        return G[n];
    }
}

[ACcentuaLtor]

class Solution { public int numTrees(int n) { int[] G = new int[n + 1]; G[0] = 1; G[1] = 1;

for (int i = 2; i <= n; ++i) {
    for (int j = 1; j <= i; ++j) {
        G[i] += G[j - 1] * G[i - j];
    }
}
return G[n];

} }

[LannyX]

代码

class Solution {
    public int numTrees(int n) {
        int[] dp = new int[n + 1];
        dp[0] = 1;
        dp[1] = 1;

        for(int i = 2; i <= n; i++){
            for(int j = 0; j < i; j++){
                dp[i] += dp[j] * dp[i - j - 1];
            }
        }
        return dp[n];
    }
}

复杂度分析

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

[cszys888]

class Solution:
    def numTrees(self, n: int) -> int:
        dp = [0]*(n + 1)
        dp[0] = dp[1] = 1
        for idx in range(2, n+1):
            for i in range(1,idx+1):
                dp[idx] += dp[i-1]*dp[idx - i]
        return dp[-1]

time complexity: O(N^2) space complexity: O(N)

[feifan-bai]

思路 1.分治

代码

class Solution:
    visited = dict()
    def numTrees(self, n: int) -> int:
        if n in self.visited:
            return self.visited.get(n)
        if n <= 1:
            return 1
        res = 0
        for i in range(1, n + 1):
            res += self.numTrees(i - 1) * self.numTrees(n - i)
        self.visited[n] = res
        return res

复杂度分析

• 时间复杂度：O(N*N)
• 空间复杂度：O(N)

[falconruo]

思路:

分治

复杂度分析:

• 时间复杂度: O(N^2)，N为给定的节点数N
• 空间复杂度: O(N)

代码(C++):

class Solution {
public:
    int numTrees(int n) {
        vector<int> dp(n + 1, 0);
        dp[0] = 1;

        for (int i = 1; i <= n; i++) {
            for (int j = 0; j < i; j++)
                dp[i] += dp[j] * dp[i - j - 1];
        }

        return dp[n];
    }
};

[zhiyuanpeng]

class Solution:
    def numTrees(self, n: int) -> int:
        dp = [1, 1] + [0] * (n-1)

        for i in range(2, n+1):
            for j in range(1, i+1):
                dp[i] += dp[j-1] * dp[i-j]
        return dp[n]

[xuhzyy]

class Solution(object):
    dp = {}

    def numTrees(self, n):
        """
        :type n: int
        :rtype: int
        """
        # dp = [0] * (n + 1)
        # dp[0] = 1
        # dp[1] = 1
        # for i in range(2, n+1):
        #     for j in range(1, i+1):
        #         dp[i] += dp[j-1] * dp[i-j]
        # return dp[-1]

        if n <= 1:
            return 1

        if n in self.dp:
            return self.dp[n]

        res = 0
        for i in range(1, n + 1):
            res += self.numTrees(i-1) * self.numTrees(n-i)
        self.dp[n] = res
        return res

[zol013]

class Solution:
    def numTrees(self, n: int) -> int:
        '''
        bst = [0] * (n + 1)
        bst[0], bst[1] = 1, 1

        for i in range(2, n + 1):
            for j in range(1, i + 1):
                bst[i]  += bst[j - 1] * bst[i - j]

        return bst[n]
        '''

        @lru_cache(None)
        def bst(l, r):
            if r <= l:
                return 1

            sum = 0
            for i in range(l, r + 1):
                left = bst(l, i - 1)
                right = bst(i + 1, r)
                sum += left * right

            return sum

        return bst(0, n - 1)

[jiaqiliu37]

class Solution:
    visited = dict()

    def numTrees(self, n: int) -> int:
        if n in self.visited:
            return self.visited[n]

        if n <= 1:
            return 1

        ans = 0
        for i in range(1, n + 1):
            ans += self.numTrees(i - 1)*self.numTrees(n-i)

        self.visited[n] = ans

        return ans

Time complexity O(n^2) Space complexity O(n)

[tongxw]

思路

笛卡尔乘积 dp[i] = sum(dp[j-1] * dp[i-j]), 1<=j<=i

class Solution {
    public int numTrees(int n) {
        int[] dp = new int[n + 1];
        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];
    }
}

TC: O(n^2) SC: O(n)

[Serena9]

代码

class Solution:
    visited = dict()

    def numTrees(self, n: int) -> int:
        if n in self.visited:
            return self.visited.get(n)
        if n <= 1:
            return 1
        res = 0
        for i in range(1, n + 1):
            res += self.numTrees(i - 1) * self.numTrees(n - i)
        self.visited[n] = res
        return res

[chengyufeng6]

class Solution { public: int numTrees(int n) { vector dp(n + 1); 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]; } }; 时间复杂度：O(n²) 空间复杂度：O(n)

[spacker-343]

class Solution {
    public int numTrees(int n) {
        int[] dp = new int[n + 1];
        dp[0] = 1;
        dp[1] = 1;
        for (int i = 2; i <= n; i++) {
            for (int j = 1; j <= i; j++) {
                dp[i] += dp[j - 1] * dp[i - j];
            }
        }
        return dp[n];
    }
}

[hdyhdy]

func numTrees(n int) int {
    dp := make([]int,n+1)
    dp[0] = 1
    for i := 1 ; i < n + 1 ; i ++ {
        for j := 1 ; j <= i ; j ++ {
            dp[i] += dp[j - 1 ] * dp[i - j]
        }
    }
    return dp[n]
}

[LAGRANGIST]

class Solution: def numTrees(self, n: int) -> int: dp = [1, 1] + [0] * (n-1)

    for i in range(2, n+1):
        for j in range(1, i+1):
            dp[i] += dp[j-1] * dp[i-j]
    return dp[n]

[stackvoid]

思路

数学 公式的推导。。。

代码

class Solution {
    public int numTrees(int n) {
        int[] G = new int[n + 1];
        G[0] = 1;
        G[1] = 1;

        for (int i = 2; i <= n; ++i) {
            for (int j = 1; j <= i; ++j) {
                G[i] += G[j - 1] * G[i - j];
            }
        }
        return G[n];
    }
}

算法分析

Time O(N^2) Space O(N)

[kite-fly6618]

思路

动态规划

代码

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

复杂度

时间复杂度：O(n2)
空间复杂度：O(n)

[demo410]

public int numTrees(int n) {
        int[] G = new int[n + 1];
        G[0] = 1;
        G[1] = 1;

        for (int i = 2; i <= n; ++i) {
            for (int j = 1; j <= i; ++j) {
                G[i] += G[j - 1] * G[i - j];
            }
        }
        return G[n];
    }

[callmeerika]

思路

动态规划

代码

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

复杂度

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

[biscuit279]

思路：

递归：ans[n] += ans[i-1] * ans[n-1]

class Solution(object):
    visited = dict()

    def numTrees(self, n):
        if n in self.visited:
            return self.visited.get(n)
        if n <= 1:
            return 1
        res = 0
        for i in range(1, n + 1):
            res += self.numTrees(i - 1) * self.numTrees(n - i)
        self.visited[n] = res
        return res

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

[shamworld]

var eraseOverlapIntervals = function(intervals) {
    let len = intervals.length;
    if(len==0) return 0;
    //通过区间最后一个元素排序
    intervals.sort((a,b)=>a[1]-b[1]);
    //最多不重叠区间数，至少为1
    let count = 1;
    //初始结尾
    let end= intervals[0][1];
    for(let inter of intervals){
        let num = inter[0];
        if(num>=end){
            count++;
            end = inter[1];
        }

    }
    return len-count;
};

[tian-pengfei]

class Solution {
public:
    int numTrees(int n) {
        vector<int> dp(n+1,0);
        dp[0]=1;
        dp[1] =1;

        for (int i = 2; i <=n; ++i) {

            for (int j = 0; j <=i-1; ++j) {
                dp[i] +=dp[i-1-j]*dp[j];
            }
        }

        return dp[n];
    }
};

[dahaiyidi]

Problem

[96. 不同的二叉搜索树](https://leetcode-cn.com/problems/unique-binary-search-trees/)

++

难度中等1547

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

---

Note

• 重要的是如何将问题转化为动态规划的问题

---

Complexity

• 时间O：n^2
• 空间O：n

---

Python

C++

class Solution {
public:
    int numTrees(int n) {
        // 状态定义：f[i]: 以i为根节点的树的个数, G[i]: 总结点数为i时，树的个数， G[n]为最终的结果
        // G[n] = f[1] + f[2] + ... + f[n]
        // 状态转移：由于f[i] = G[i - 1] * G[n - i],
        // 则G[i] = f[1] + f[2] + ... + f[i] 
        // = G[0] * G[i - 1] + G[1] * G[i - 2] + ... + G[i - 1] * G[i - i]，这就是状态方程。
        vector<int> dp(n + 1, 0);
        dp[0] = 1;
        dp[1] = 1;
        for(int i = 2; i <= n; i++){
            for(int j = 0; j <= i - 1; j++){
                dp[i] += dp[j] * dp[i - 1 - j];
            }
        }
        return dp[n];
    }
};

From : https://github.com/dahaiyidi/awsome-leetcode

[googidaddy]

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

[hx-code]

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

[superduduguan]

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

[Hacker90]

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