```
public class Solution {
public int NumTrees(int n)
{
int[] memo = new int[n + 1];
return subTrees(n, memo);
}
private int subTrees(int totalNum, int[] memo)
{
if (totalNum == 0) return 1;
if (totalNum == 1) return 1;
int sum = 0;
for (int iter = 0; iter < totalNum; iter++)
{
int leftTreeLength = iter;
int rightSubTreeLength = totalNum - iter - 1;
if(memo[leftTreeLength] == 0)
{
memo[leftTreeLength] = subTrees(leftTreeLength, memo);
}
if (memo[rightSubTreeLength] == 0)
{
memo[rightSubTreeLength] = subTrees(rightSubTreeLength, memo);
}
sum += memo[leftTreeLength] * memo[rightSubTreeLength];
}
return sum;
}
}
```