1
class Solution {
2
 public:
3
  int catalan(int n, vector<int> &dp) {
4
    if (n <= 1) return 1;
5

6
    int ans = 0;
7
    for (int i = 0; i < n; i++) {
8
      ans += catalan(i, dp) * catalan(n - 1 - i, dp);
9
    }
10

11
    return ans;
12
  }
13
  int numTrees(int n) {
14
    vector<int> dp(n + 1, -1);
15

16
    dp[0] = 1;
17
    dp[1] = 1;
18

19
    for (int i = 2; i <= n; i++) {
20
      int ans = 0;
21
      for (int j = 0; j < i; j++) {
22
        ans += dp[j] * dp[i - 1 - j];
23
      }
24
      dp[i] = ans;
25
    }
26

27
    return dp[n];
28

29
    // return catalan(n,dp);
30
  }
31
};