题解 | #有多少个不同的二叉搜索树#
有多少个不同的二叉搜索树
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的种数。