96. Unique Binary Search Trees

子樹會是一個組合

https://appktavsiei5995.pc.xiaoe-tech.com/p/t_pc/course_pc_detail/image_text/i_62987940e4b01a4852072f8c

Catalan Number:

https://stackoverflow.com/questions/27371612/catalan-numbers-recursive-function-time-complexity

T :O(n^2)

S:O(n^2)

```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;
    } 
} 
```