solution.cpp

#include <stdc++.h>
using namespace std;
class Solution
{
public:
	int numTrees(int n)
	{
		vector<int> sum(n + 1);
		sum[0] = 1;
		for (int i = 1; i <= n; i++)
		{
			for (int j = 0; j < i; j++)
			{
				sum[i] += sum[j] * sum[i - j - 1];
			}
		}
		return sum[n];
	}
}