Niuke: how many different binary search trees are there

  I made it very clear on Li Kou , Interesting derivation ：

Power button

First , set up F(i,n) Express n Length of the sequence with i The number of binary search trees divided for the root node ,G(n) Length n The number of binary search trees of the sequence of , Obviously ：

And obviously ,F(i, n) In fact, the number of can be determined by two subtrees G Obtained , As shown below ： 

  And then we derive G Recursive expression of ：

The code is as follows ：

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;
    cin>>n;
    vector<int> G(n+1);
    G[0]=G[1]=1;
    for(int i=2;i<=n;++i){
        for(int j=0;j<=i;++j){
            G[i]+=G[j-1]*G[i-j];
        }
    }
    cout<<G[n];
    return 0;
}