题目
给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种？返回满足题意的二叉搜索树的种数。
示例 1：
输入：n = 3 输出：5
示例 2：
输入：n = 1 输出：1
解题
方法一：动态规划
思路一：
举个例子：
当n=3时
元素1为头结点搜索树的数量 = 右子树有2个元素的搜索树数量 * 左子树有0个元素的搜索树数量
元素2为头结点搜索树的数量 = 右子树有1个元素的搜索树数量 * 左子树有1个元素的搜索树数量
元素3为头结点搜索树的数量 = 右子树有0个元素的搜索树数量 * 左子树有2个元素的搜索树数量
有2个元素的搜索树数量就是dp[2]。
有1个元素的搜索树数量就是dp[1]。
有0个元素的搜索树数量就是dp[0]。
dp[3]=dp[2]∗dp[0]+dp[1]∗dp[1]+dp[0]∗dp[2]
所以,相当于j从0开始遍历到j =i-1
dp[i]+=dp[j]∗dp[i−1−j]
class Solution { public: int numTrees(int n) { vector<int> dp(n+1); dp[0]=1; for(int i=1;i<=n;i++){ for(int j=0;j<i;j++){ dp[i]+=dp[j]*dp[i-1-j]; } } return dp[n]; } };
思路二：
class Solution { public: int numTrees(int n) { vector<int> dp(n+1); 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]; } };
