动态规划 二叉搜索树的种类
【问题描述】
给定从1到n的n个编号的节点，问这些节点可以构成多少种不同的二叉搜索树？
当n=1时，只有1种
当n=2时候，有2种
- 以1为根节点
- 以2为根节点
当n=3时，有3大类，共5种
- 以1为根节点
- 以2为根节点
- 以3为根节点
【求解思路】
对于1到n个节点，其最终的二叉搜索树的种类可以分为n大类；
即以1为根节点
以2为根节点
以3为根节点
......
可以发现，当以k为根节点时：
其前面1节点到k-1节点必定位于其左子树
而k+1节点到n节点必定位于其右子树
而左右子树的具体结构种类又划归为子问题
递推公式：