給定一個整數 n，求以 1 … n 為節點組成的二叉搜索樹有多少種？

解題思路

*數組含義：dp[i] i個節點的不同組成結構
狀態轉移：任取節點為根節點，遍歷左右子樹可能出現的個數,dp[i]=dp[left]dp[right]
初始化：dp[0]=1 空節點也作為一種情況

代碼

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