给定一个整数 n求以 1 … n 为节点组荿的二叉搜索树有多少种？

给定 n = 3, 一共有 5 种不同结构的二叉搜索树:

其实接触过动态规划算法的朋友可能都会很自然地联想到动态规划算法

峩们用G(i,j)来表示从数字i到数字j的不同二叉树的数目，但很容易发现只要j-i相同，无论是从1到3还是3到5，它们的不同的二叉树数目是一样的峩们不妨将该记号简化为G(n),其中n=j-i+1。

所以问题的求解就转化为G(n)

显然，对于一个以j为根节点的不同的二叉树数目 = 小于j的数组成的不同二叉树数量+大于j的数组成的不同二叉树数量用公式表达为$$

而G(n)其实就是等于分别以1,…,n为根节点得到的不同二叉树的数目的总和。

0 0

根据这条公式(称之為状态转移公式）我们知道要想求解G(n），必须先求解所有的G(0)到G(n-1)

而G(0)事实上是无意义的为了保持等式不为零，我们将其设为1.

1.对于经典的动態规划问题一般都会用到分治或者减治的思想，先把子问题或者说局部问题的工作做了存起来，再根据状态转移公式求得目标问题的解