1. Topic describes \color{DodgerBlue}{1.

Given an integer n, how many binary search trees are composed of exactly n nodes with different values from 1 to n? Returns the number of binary search tree species that satisfy the problem.

Difficulty: Medium

Example 1:

Input: n = 3 Output: 5Copy the code

Example 2:

Input: n = 1 Output: 1Copy the code


2. Their thinking \color{DodgerBlue}{2.

  1. Integers of 1− N1 − N1 − N, each of which can be used as a root node, and then the left and right subtrees can be used as binary search trees
  2. So we can use dynamic programming to decompose the problem step by step
  3. Assuming G(n)G(n)G(n) represents the tree F(I)F(I)F(I)F(I) is the tree of binary search tree with node I as the root, then G(n)=F(1)+F(2)+… +F(i)… +F(n)G(n) = F(1)+F(2)+… +F(i)… +F(n)G(n)=F(1)+F(2)+… +F(i)… +F(n)

G ( n ) = ∑ i = 1 n F ( i ) G(n)=\sum_{i=1}^{n}F(i)
  1. I as a root node, the left and right subtrees respectively [1… I – 1] [1… I – 1] [1… I – 1] and [I + 1… n] [I + 1… n] [I + 1… n], Their binary tree tree G respectively (I – 1), G (n – I) G (I – 1), G (n – I) G (I – 1), G (n – I)
  2. So F (I) = G (I – 1) ∗ G n – (I) F (I) = G (I – 1) * (n – I) G F (I) = G (I – 1) ∗ G (n – I), the situation about number is the product of the two subtrees
  3. So can conclude G (n) = ∑ [G ∗ (I – 1) G (n – I)], 1 < = I < = nG (n) = \ sum [G (I – 1) * G (n – I)], 1 < = I < = nG (n) = ∑ [G (I – 1) ∗ G n – (I)], 1 < = I < = n (here is the final sum mathematical formula)

  4. G ( n ) = [ G ( 0 ) G ( n – 1 ) ] + [ G ( 1 ) G ( n – 2 ) ] + [ G ( 2 ) G ( n – 3 ) ] + . . . + [ G ( n – 2 ) G ( 1 ) ] + [ G ( n – 1 ) G ( 0 ) ] G(n) = [G(0)G(n-1)] + [G(1)G(n-2)] + [G(2)G(n-3)] + … + [G(n-2)G(1)] + [G(n-1)G(0)]

G ( n ) = ∑ i = 1 n G ( i – 1 ) ∗ G ( n – i ) G(n)=\sum_{i=1}^{n}G(i-1)*G(n-i)
  1. For the initial boundary, when there is an empty tree or only one node, G(0)=G(1)=1G(0) =1G(0) =G(1)=1, there is only one case
  2. Ref:leetcode-cn.com/problems/un…


3. J a v a S c r i p t code \ color {DodgerBlue} {3} JavaScript code 

/ * * *@param {number} n
 * @return {number}* /
var numTrees = function(n) {
    let dp = new Array(n + 1).fill(0)
    dp[0] = 1
    dp[1] = 1
    for(let j = 2; j <= n; j++){ // Since we know 0 and 1, we need dp(n), so j starts at 2
        for(let i = 1; i <= j; i++) { 
            dp[j] += dp[i-1] * dp[j-i] 
        }
    }
    return dp[n]
};
Copy the code