[dynamic programming] different binary search trees

Give you an integer n , Seek just by n Composed of nodes with node values from 1 To n Different from each other Binary search tree How many kinds? ？ Returns the number of binary search trees satisfying the meaning of the question .

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

Definition ：$dp[i]$​ Indicates that the slave node is $i$ The number of different binary search trees

The boundary conditions ：$dp[0]=1,dp[1]=1,dp[2]=2$​, No nodes , The empty set is unique ;1 Nodes , A kind of ;2 Nodes , Two kinds of ​​

State transition equation ：$dp[i]=\sum _{j=0}^{i-1}dp[j]\ast dp[i-j-1]$

explain ：

When there are no nodes , The empty set is unique ;

1 Nodes , A kind of ;

2 Nodes , Two kinds of , Namely , Given a node , The left subtree 1 Nodes , Right subtree 0 Nodes , And given a node , The left subtree 0 Nodes , Right subtree 1 Nodes

3 Nodes ,5 Kind of , Namely , Given a node ,① The left subtree 2 Nodes , Right subtree 0 Nodes ;② The left subtree 1 Nodes , Right subtree 1 Nodes ;③ The left subtree 0 Nodes , Right subtree 2 Nodes . For the situation 1 And circumstances 3, They can be expressed as $dp[2]\ast dp[0]$​ and $dp[0]\ast dp[2]$​​ The situation of , Others in the same way , That is, the corresponding state transition equation .

class Solution:
    def numTrees(self, n: int) -> int:
        #  Dynamic programming method 
        #dp[i] = Σdp[k]*dp[i-k-1]

        dp = [0]*(n+1)
        dp[0] = 1   # 0 Elements 
        dp[1] = 1   # 1 Elements 
        if n<=1: return dp[n]

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

The complexity of this method is O(n^2), You can use mathematical methods , Get the general term formula （ Carter LAN number ）, Reduce complexity