1.题目

2.思路

由于要用到dp[n]所以dp数组一开始至少要开到dp(n+1)。

（1）确定状态
首先要看大问题能否划分为子问题：二叉搜索树的中序遍历即从小到大排列的序列，而现在既然给定1~n连续数，假设当前的根结点为j，那么j左边有j-1个连续数，现在的子问题就是要求出这j-1能构成多少个二叉搜索树，而且这个值保存（记忆化）下来还能给后面的运算直接使用。
所以可令状态$dp[i]$表示用1到i结点组成的二叉搜索树的个数。

（2）转移方程
$dp[i]+=dp[j-1]\ast dp[i-j]$，j-1是j为头结点的左子树结点数，i-j是j为头结点的右子树结点数。注意这个式子是累加的过程。

（3）初始条件+边界情况
dp[0]=1。
咋一想可能会觉得是0，但是当i=1，j=1时，dp[i]+=dp[j-1]*dp[i-j]里的dp[0]*dp[0]就等于0了（1个结点的二叉搜索树个数为1，而非）故错误；或者说空树也是一颗树。

（4）计算顺序
i从1到n，j从1到i。

3.代码

class Solution {
public:
    int numTrees(int n) {
        vector<int>dp(n+1);//而非开到n大小
        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];//1~n组成的二叉搜索树个数
    }
};

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
 

4.其他方法

之前学408也有说到结论：n个结点构成的二叉搜索树的种类数为卡特兰数，关于卡特兰数可以参考这篇灰常详细https://www.cnblogs.com/RioTian/p/13709159.html。

文章来源: andyguo.blog.csdn.net，作者：山顶夕景，版权归原作者所有，如需转载，请联系作者。

原文链接：andyguo.blog.csdn.net/article/details/113502174