```java
class Solution {
public int numTrees(int n) {
Integer[][] memo = new Integer[n+1][n+1];
return dfs(1, n, memo);
}
private int dfs(int lo, int hi, Integer[][] memo) {
if (lo > hi) {
return 1;
}
if (memo[lo][hi] != null) {
return memo[lo][hi];
}
int result = 0;
for (int i = lo; i <= hi; i++) {
int left = dfs(lo, i-1, memo);
int right = dfs(i+1, hi, memo);
result += left*right;
}
return memo[lo][hi] = result;
}
}
```
T: O(n^2)
S: O(n)
```java
class Solution {
public int numTrees(int n) {
Map<Integer, Integer> memo = new HashMap<>();
return dfs(n, memo);
}
private int dfs(int n, Map<Integer, Integer> memo) {
if (n == 0 || n == 1) {
return 1;
}
if (memo.containsKey(n)) {
return memo.get(n);
}
int result = 0;
for (int i = 1; i <= n; i++) {
int left = dfs(i-1, memo); // n = 3, i = 1, left has 0
int right = dfs(n-i, memo); // right has 2, and left 1 is root
result += left * right;
}
memo.put(n, result);
return result;
}
}
```