动态规划Leetcode96.不同的二叉搜索树

给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种？返回满足题意的二叉搜索树的种数。

解题步骤如下：

1. 二叉搜素树的相关概念
2. 寻找规律
3. 思路建立
4. 代码实现

1.二叉搜索树的相关概念

①：若左子树不空，则左子树所有节点的值均小于它的根节点的值。
②：若右子树不空，则右子树所有节点的值均大于它的根节点的值。
③：它的左右子树也分别为二叉搜索树。

2.寻找规律

当n=1时，二叉搜索树如图：

如图所示，n=1时，有1棵二叉搜索树

当n=2时，二叉搜索树如图：

• [ ]

如图所示，n=2时，有2棵二叉搜索树

当n=3时，二叉搜索树如图：

当n=3时，我们可以仔细研究一下它们的情况。

• 以1为头结点的二叉搜索树，都是左节点为0；且右节点布局与n=2时的布局一样（这里如果说数值都不一样云云，请记住题目只求种类不是具体的每一棵树）
• 以3为头结点的二叉搜索树，都是右节点为0；且左节点与n=2时的布局一样
• 以2为头结点的二叉搜索树，左右子树各有1个节点，形态也和n=1时只有一棵树的布局一样

那么可以上述规律可以整合为：
dp[3]=以1为头结点的搜索树数量+以2为头结点的搜索树数量+以3为头结点的搜索树数量

• 以1为头结点的搜索树数量=左子树元素为0的搜索树的数量x右子树元素为2的搜索树数量
• 以2为头结点的搜索树数量=左子树元素为1的搜索树的数量x右子树元素为1的搜索树数量
• 以3为头结点的搜索树数量=左子树元素为2的搜索树的数量x右子树元素为0的搜索树数量

数量为0的搜索树数量为dp[0]
数量为1的搜索树数量为dp[1]
数量为2的搜索树数量为dp[2]

固有：dp[3]=dp[0]dp[2]+dp[1]dp[1]+dp[2]dp[0]
接下来把思路泛化成题目需要的样子

3.思路建立

1.定义dp数组含义
dp[i]为1到i个不同元素组成的二叉搜索树节点为dp[i]；dp[n]就是题意要求的搜索树种数。
2.推导公式
由上述推导公式可知，我们需要明确头结点，左子树数量，右子树数量。故我们在这里设j作为头结点，那么左子树数量自然为（j-1）个，右子树数量为（i-j）个。
我们可以得公式：dp[i]=dp[j-1]*dp[i-j]
(可能会有朋友疑问为什么用相乘，打个比方说n=10的二叉搜索树，左子树情况有5种，右子树情况情况有8种，要想得出所有的情况是不是应该用相乘？)
当你用以上公式从1开始推导到n,你就会发现上述公式只是推导了某一个具体的i值，如果需要从1开始推导到n,我们需要做一个累加运算，从i=1开始运算，算完了i=1的值时，把它的结果累加到下一轮i=2的运算，这样我们计算到n时，就把1+2+3+......+n的值都没有差错地累加上了。

故最后的递推公式为dp[i]+=dp[j-1]*dp[i-j]
3.初始化
只需要考虑dp[0]，若二叉搜索树左右子树任意一方为空，他们结果相乘为0是不合理的，故dp[0]=1。
4.遍历顺序
由递推公式dp[i]+=dp[j-1]dp[i-j]很容易看出，dp[i]是由比i小的状态数推导出来的，故是从小的数遍历到大的数（int i =1;i<=n;i++）
在i的循环底下，接着进行j的循环。j是头结点，从1的头结点开始，一直遍历到i为头节点的情况。固有（int j=1;j<=i;j++）
（不要懵逼为什么是i，我们定义的dp[i]里的i就是i个不同元素组成的搜索树的种类！）

4.代码实现

点击查看代码

class Solution {
public:
int numTrees(int n) {
vector 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];
}
};