学步园

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

其实就是计算卡特兰数。

class Solution {
public:
    int numTrees(int n) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        
    	if ( n<=0 )
			return 0;
		vector<int> dp(n+1,0);
		dp[0]=1;
		
		for(int i=1;i<=n;i++)
		{
			for(int left=0;left<i;left++)
			{
				dp[i]+=dp[left]*dp[i-left-1];
			}
		}
		return dp[n];
    }
};