7. 不同的二叉搜索树（LeetCode-96）
题目
给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种？返回满足题意的二叉搜索树的种数。
示例 1：
输入：n = 3 输出：5
示例 2：
输入：n = 1 输出：1
提示：
1 <= n <= 19
思路
这里用代码随想录的图分析一下
n = 1
n = 2
n = 3
可以分3种情况
1.元素1为头结点时，没有比1小的元素了，所以左子树为空，右子树元素个数为二，就有 dp[2] 种组合。为什么是 dp[2] 种，题目不是说是由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种吗？这里呢其实大家要明白 dp[i] 的含义，也就是先定dp数组——i 个不同元素节点组成的互不相同的二叉搜索树有 dp[i] 种。我这里去掉了节点值从 1 到 n ，因为对于元素个数为2的二叉搜索树来说，无论它的元素值是 1 ， 2 还是 2 ， 3，排列组合的结果都是一样的！
2.元素2为头结点时，左子树元素个数为一，右子树元素个数也为一
3.元素3为头结点时，左子树元素个数为二，右子树元素个数也为零
4.所以 d p [ 3 ] = d p [ 2 ] ∗ d p [ 0 ] + d p [ 1 ] ∗ d p [ 1 ] + d p [ 0 ] ∗ d p [ 2 ]
五部曲
1.dp[i] 含义： i 个不同元素节点组成的互不相同的二叉搜索树有 dp[i] 种
2.变量 j 从 0 遍历至 i-1 ，dp[i] 初值为零
d p [ i ] = d p [ i ] + d p [ j ] ∗ d p [ i − j − 1 ]
3.dp[0]=1 从定义上来讲，空节点也是⼀颗⼆叉树，也是⼀颗⼆叉搜索树
4.节点数为i的状态是依靠 i之前节点数的状态,所以从前往后
5.测试用例
代码展示
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 - j - 1]; } } return dp[n]; } };
8. 小结
卡尔哥的方法是真的好用，写dp代码没多少，主要是五部曲写出思路。代码随想录yyds！
