题解 | #有多少个不同的二叉搜索树#
有多少个不同的二叉搜索树
https://www.nowcoder.com/practice/16d23f940a084023b3be6019262589dc
import sys
for line in sys.stdin:
a = line.split()
n = int(a[0])
d = dict()
def dp(s, e):
if s >= e :
return 1
t = 0
for i in range(s, e+1):
if (s, i-1) in d:
l = d[(s, i-1)]
else:
l = dp(s, i-1)
d[(s, i-1)] = l
if (i+1, e) in d:
r = d[(i+1, e)]
else:
r = dp(i+1, e)
d[(i+1, e)] = r
t += l * r
return t
print(dp(1, n))
从1到n的二叉搜索树个数可以这样找， 以1为根节点，剩下的作为右子树， 以2为根节点，左侧的为左子树，右侧的为右子树，...，一直到n，然后把它们的种数相加既是答案。同样划分出的子树又能以各个值为根节点继续划分左右，直到划分的开始下标>=结束下标。
以n为节点，左侧数据为左子树，右侧数据为右子树，总的种数 = 左子树个数*右子树个数。
单纯递归有很多重复计算，所以引入 d[(i,j)] 记录 从i到j的种数。
