classSolution{public:intnumTrees(intn){// G[i] := # of unique BST's that store values 1..ivector<int>G(n+1);G[0]=1;G[1]=1;for(inti=2;i<=n;++i)for(intj=0;j<i;++j)G[i]+=G[j]*G[i-j-1];returnG[n];}};
classSolution{publicintnumTrees(intn){// G[i] := # of unique BST's that store values 1..iint[]G=newint[n+1];G[0]=1;G[1]=1;for(inti=2;i<=n;++i)for(intj=0;j<i;++j)G[i]+=G[j]*G[i-j-1];returnG[n];}}
classSolution:defnumTrees(self,n:int)->int:# G[i] := # Of unique BST's that store values 1..iG=[1,1]+[0]*(n-1)foriinrange(2,n+1):forjinrange(i):G[i]+=G[j]*G[i-j-1]returnG[n]