学步园

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

一个简单的DP：

#include<iostream>
#include<vector>
#include<map>
using namespace std;


class Solution {
public:
	int numTrees(int n)
	{
		int ans=0;
		map<int,int> rec;
		ans+=_cal(n,rec);
		return ans;
	}
	int _cal(int n,map<int,int>& rec)
	{
		if ( n==0 )
			return 1;
		if ( n==1 )
			return 1;
		map<int,int>::iterator it=rec.find(n);
		if ( it!=rec.end())
		{
			return it->second;
		}
		int ans=0;
		for(int i=0;i<n;i++)
		{
			ans+=_cal(i,rec)*_cal(n-i-1,rec);
		}
		rec.insert(it,pair<int,int>(n,ans));
		return ans;
	}	
};

int main()
{
	int n;
	Solution so;
	while((cin>>n)&&n!=-1)
	{
		int ans=so.numTrees(n);
		cout << ans <<endl;
	}
}