目录
1、题目描述
2、思路：动态规划
2.2、确定递推公式
2.3、dp数组初始化
2.4、确定遍历顺序
3、C++实现如下
1、题目描述
给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种？返回满足题意的二叉搜索树的种数。
示例 1：
输入：n = 3
输出：5
示例 2：
输入：n = 1
输出：1
提示：
1 <= n <= 19
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/unique-binary-search-trees
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
2、思路：动态规划
首先仔细都题目，寻找以下n与搜索树数量的关系。
n为1时，搜索树的数量为1；n为2时，搜说树的数量为2。
n为3时，可以有三种情况：
头节点为1时，左子树有0个节点，右子树有2个节点，2个节点的分布情况与n为2时的情况相同。
头节点为2时，左子树有1个节点，右子树有1个节点，1个节点的分布情况与n为1时的情况相同。
头节点为3时，左子树有2个节点，右子树有0个节点，2个节点的分布情况与n为2时的情况相同。
所以我们便可以找到递推公式之间的关系：dp[3] = dp[2] * dp[0] + dp[1] * dp[1] + dp[0] * dp[2]
2.1、确定dp数组及下标的含义
dp[i]表示n=i时的最大搜索树的数量。
2.2、确定递推公式
dp[i] += 以j为头结点的搜索树数量 = dp[以j为头结点左子树节点数量] * dp[以j为头结点右子树节点数量]
j相当于是头结点的元素，从1遍历到i为止。
2.3、dp数组初始化
dp[0]相当于没有子树的情况，自然是1种分布情况。
dp[1]则是以1为头节点，左子树数量为0，右子树数量为0，dp[0]*dp[0] = 1；
所以初始化为dp[0] = 1即可。
2.4、确定遍历顺序
从递归公式：dp[i] += dp[j - 1] * dp[i - j]可以看出，节点数为i的状态是依靠 i之前节点数的状态。
3、C++实现如下
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 = 1;j<=i;++j){dp[i] += dp[j-1]*dp[i-j];}}return dp[n];}
};
