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);
代码:
1 class Solution {
2 public:
3 int numTrees(int n) {
4 if (n == 0)
5 return 0;
6 vector<int> res(n+1, 0);
7 res[0] = res[1] = 1;
8
9 for (int i = 2; i <= n; ++i) {
10 for (int j = 0; j < i; ++j) {
11 res[i] += res[j] * res[i-1-j];
12 }
13 }
14
15 return res[n];
16 }
17 };
Leetcode测试集中没有考察n为0的情况,我认为n为0时还是有意义的,应该返回0。