第29天。

今天的题目是Unique Binary Search Trees:

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

对于这种问题一般都可以用递归去做的，我们尝试的找一下递归式。

n=1 -> 1 n=2 -> 2 n=3 -> 5

我们考虑n=3时的情况,这时这棵树种包含三个值1,2,3,这说明树根的可能是1,2,3中的一个值：

• 当root=1时，2,3只能放在右子树。现在只考虑2,3两个值，由于BST的性质,右子树也必须是BST，则此时问题转换成求numsTrees(2).
• 当root=2时，左边必定是1,右边必定是3.
• 当root=3时，左边必定是1,2，同样转换成numsTrees(2).

我们再考虑一下n=5时的情况：

• root=3，左子树必定是是包含1,2的BST，右子树必定是包含4,5的BST，此时种类为numsTree(5-3)*numsTrees(3-1)。

所以我们可以找到递推式：

• n < 2 -> numsTrees(n) = 1
• n >= 2 -> numsTrees(n) = numsTrees(1)*numsTrees(n-1) + numsTrees(2)*numTree(n-2) + ... + numsTree(n-1)*numsTrees(1);

所以我们写出一个递归的解决方案:

1
int numTrees(int n) {
2
    if (n <= 1) return 1;
3

4
    int ret = 0;
5
    for(int i = 1;i <= n;i++) {
6
        int left = i-1;
7
        int right = n-i;
8
        ret += numTrees(left)*numTrees(right);
9
    }
10
    return ret;
11
}

但是这里会超时，很明显这里可以用动态规划来优化:

1
int numTrees(int n) {
2
    vector<int> ret(n+1);
3
    ret[0] = 1;
4
    ret[1] = 1;
5
    for(int i = 2;i <= n;i++) {
6
        for(int j = 1;j <= i;j++)
7
            ret[i] += ret[j-1]*ret[i-j];
8
    }
9
    return ret[n];
10
}

dicuss中基本都是和上面类似的解法，除了一个:

1
int numTrees(int n) {
2
    //cantalan树
3
    //C(2n,n)/(n+1)
4
    long long ans =1;
5
    for(int i=n+1;i<=2*n;i++){
6
        ans = ans*i/(i-n);
7
    }
8
    return ans/(n+1);
9
}

emmm,说实话，我没看懂，但是这个方法的确是最快的，只需要O(n)的时间，O(1)的空间。