Unique Binary Search Trees

Given n, how many structurally unique BST’s (binary search trees) that store values 1…n?

给出序列 n(1……n),求能组成多少个不同的 BST(二叉搜索树) 树。

For example,Given n = 3, there are a total of 5 unique BST’s.

比如,给出 n = 3,这里一共列举五个不同的 BST 树。


解体思路

解法一

这里可能要接触一个新鲜的事物,叫做卡特兰数列(Catalan number),类似斐波那契数列,后者是若干加法求和,前者类似若干乘法求和,具体公式:

catalan

而本题的答案刚好和此数列一致,所以,具体(无脑)算法如下:

Hello world!
文章已创建 197

相关文章

开始在上面输入您的搜索词,然后按回车进行搜索。按ESC取消。

返回顶部