题解 | 不同的二叉搜索树

import java.util.*;


public class Solution {
    /**
     *使用 卡特兰数（Catalan）公式  
    
     * @param n int整型
     * @return int整型
     */
    public int numTrees1 (int n) {
        int num = 1;
        for (int i = 0; i < n; i++) {
            num = 2 * (2 * i + 1) * num / (i + 2);
        }
        return  num;
    }

  /**
  
    循环 或者递归处理  以 i 为根的 BST 数量为 C(i-1) × C(n-i)
  */
    public static int numTrees (int n) {

        int[] arr = new int[n + 1];
        arr[0] = 1;

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= i; j++) {
                arr[i] += arr[j - 1] * arr[i - j] ;
            }
        }
        return   arr[n];
        // write code here
    }
}