[LeetCode]96. Unique Binary Search Trees

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
2
3
4
5
1         3     3      2      1
\ / / / \ \
3 2 1 1 3 2
/ / \ \
2 1 2 3

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
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
int numTrees(int n) {
vector<int> dp(n+1, 0);
dp[0] = dp[1] = 1;

for (int i=2; i<=n; i++){
for (int j=1; j<=i; j++)#根节点分别为:1-i
dp[i] += dp[j-1] * dp[i-j];
}

return dp[n];
}
};

References

https://zh.wikipedia.org/wiki/%E5%8D%A1%E5%A1%94%E5%85%B0%E6%95%B0

https://www.cnblogs.com/grandyang/p/4299608.html

您的支持就是我更新的最大动力!谢谢!