Given n, how many structurally unique BST's (binary search trees) that store values 1...n?
For example,
Given n = 3, there are a total of 5 unique BST's.
1 3 3 2 1
\ / / / \ \
3 2 1 1 3 2
/ / \ \
2 1 2 3
解题:
单纯的看做一个数列题:1, 2, 5, 14, 42, 132, ... , 求通项。
这是一个典型的卡塔兰数,中国人明安图比卡塔兰早100多年就发现了这种数列,其实更应该叫明安图数。
程序实现不用这么做,不过还是给出通项公式:f(n) = (2n)! / [(n+1)! * n!];
在原列前补充一个值为1的0位:1, 1, 2, 5, 14, 42, 132, ...
则从新数列第3个数(2)开始,f(n) = f(0) * f(n-1) + f(1) * f(n-2) + ... + f(n-1) * f(0);
代码:
class Solution {
public:
int numTrees(int n) {
if (n == )
return ;
vector<int> res(n+, );
res[] = res[] = ; for (int i = ; i <= n; ++i) {
for (int j = ; j < i; ++j) {
res[i] += res[j] * res[i--j];
}
} return res[n];
}
};
Leetcode测试集中没有考察n为0的情况,我认为n为0时还是有意义的,应该返回0。