leetcode--96. 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         3     3      2      1
           /     /      /       
     3     2     1      1   3      2
    /     /                        
   2     1         2                 3

2、思路：对于[st, end]范围的数来说，任一数字i都可以作为根节点。那么i就把数字分为3部分，[st, i - 1] + i + [i + 1, end]。[st, i - 1] 和 [i + 1, end]形成子问题，组成BST。递归解决。

那么这两个子问题是什么关系呢？它们分别生成的子树数量的关系应该是乘法的关系。

3、代码实现

 1 class Solution {
 2 public:
 3     int numTrees(int n) {
 4         return unique_bst(1, n);
 5     }
 6     
 7     int unique_bst(int st, int end){
 8         if (st >= end) {
 9             return 1;
10         }
11         int bst_num = 0;
12         for (int i = st; i <= end; i++) {
13             bst_num += unique_bst(st, i - 1) * unique_bst(i + 1, end);
14         }
15         return bst_num;
16     }
17 };

4、优化

上面解法在leetcode上面submit是TLE的。那么需要一个更优化的方法。其实从代码中可以看出，[st, end]范围生成的BST与具体的数字没有关系，只与数字的数量有关系，也就是end - st 的值有关系。那么可以采用缓存end - st的结果的方法来消除重复计算。代码如下：

 1 class Solution {
 2 public:
 3     int numTrees(int n) {
 4         int cache[n] = {0};
 5         return unique_bst(cache, 1, n);
 6     }
 7     
 8     int unique_bst(int cache[], int st, int end){
 9         if (st >= end) {
10             return 1;
11         }
12         if (cache[end - st] > 0) {
13             return cache[end - st];
14         }
15         int bst_num = 0;
16         for (int i = st; i <= end; i++) {
17             bst_num += unique_bst(cache, st, i - 1) * unique_bst(cache, i + 1, end);
18         }
19         cache[end - st] = bst_num;
20         return bst_num;
21     }
22 };

以上解法在leetcode上面submit可以通过。可以进一步优化成dp，自底向上计算。代码如下：

 1 class Solution {
 2 public:
 3     int numTrees(int n) {
 4         int cache[n + 1] = {0};
 5         cache[0] = 1;
 6         for (int i = 1; i <= n; i++) {
 7             for (int j = 1; j <= i; j++) {
 8                 cache[i] += cache[j - 1] * cache[i - j];
 9             }
10         }
11         return cache[n];
12     }
13 };

5、api

无