題目
給你一個整數 n ，求恰由 n 個節點組成且節點值從 1 到 n 互不相同的 二叉搜索樹 有多少種？返回滿足題意的二叉搜索樹的種數。
示例 1：
輸入：n = 3
輸出：5
示例 2：
輸入：n = 1
輸出：1

解題思路
本題首先得找到規律，通過推演可以發現存在遞推關系，用dp[i]表示數字i可以表示成dp[i]種搜索二叉樹，如dp[3]=dp[0]*dp[2] + dp[1]*dp[1] + dp[2]dp[0]. 初始化dp[0]=1,因為空樹是搜索二叉樹，初始化dp[1]=1.

代碼實現

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