Question
Given n, how many structurally unique BST’s (binary search trees) that store values 1 … n?
Example:
Input: 3
Output: 5
Explanation:
Given n = 3, there are a total of 5 unique BST’s:
1 | 1 3 3 2 1 |
Solution
分析
这道题是根本不会,之后看到解法说使用动态规划,自己想解法,觉得dp[i]表示1-i时可以构建的二叉树数,可以发现,dp[i] dp[i-1],dp[i]应该是在dp[i-1]时,第i个节点在i-1个节点的基础上,i出现的位置有三种情况:父结点,把i-1看做一个整体,此时bst可能数为dp[i-1];叶子节点,同样把i-1个节点看做一个整体,把i挂在整体上,也有dp[i-1]种情况;另外,位于中间节点,但一定是在根节点的右子树上,这个数我就求不出来了!没办法,只能看答案了。╮(╯▽╰)╭
这道题是明安图数(卡塔兰数)的一个例子。明安图数是组合数学中一个常在各种计数问题中出现的数列。一般项公式为
递推关系为:
也满足:
组合数学中有非常多的组合结构可以用卡塔兰数来计数。比如:
- 所有包含n组括号()的合法运算式的个数
- n个节点组成不同构二叉树的方案数
- etc
这里正好是卡塔兰数的一种应用,表示二叉树的方案数。应用它的递推关系。dp[i]表示i个节点时可以组成的不同构bst的方案数。比如i=3, $dp[3] = dp[0] dp[2] + dp[1]dp[1] + dp[3] * dp[0]$
表示当1为根节点,左子树的组合数为dp0,右子树为dp2;当2为根;当3为根,三种情况之和。
解法
1 | class Solution { |
References
https://zh.wikipedia.org/wiki/%E5%8D%A1%E5%A1%94%E5%85%B0%E6%95%B0