学步园

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

思路：

典型的动态规划题目。

BST(n) = Sum(i, 1, n, BST(i - 1) * BST(n - i))

其中(i, 1, n)表示i的取值范围从1到n。

题解：

class Solution {
public:
    vector<int> history;
    
    Solution()
    {
        history.push_back(1);
        history.push_back(1);
        history.push_back(2);
    }
    
    int numTrees(int n) 
    {
        while(history.size() <= n)
        {
            int last = history.size();
            int accumu = 0;
            for(int i = 1 ;i <= last; ++i)
                accumu += history[i - 1] * history[last - i];
            history.push_back(accumu);
        }
        
        return history[n];
    }
};