题目：

题解：

1. 方法一：动态规划

思路：

标签：动态规划
假设n个节点存在二叉排序树的个数是G(n)，令f(i)为以i为根的二叉搜索树的个数，则
G(n) = f(1) + f(2) + f(3) + f(4) + … + f(n)
当i为根节点时，其左子树节点个数为i-1个，右子树节点为n-i，则
f(i) = G(i-1)*G(n-i)
综合两个公式可以得到卡特兰数公式
G(n) = G(0)*G(n-1)+G(1)*G(n-2)+…+G(n-1)*G(0)

特别的，对于边界情况，当序列长度为 1 （只有根）或为 0 （空树）时，只有一种情况。亦即：
G(0) = 1，G(1) = 1

2. 方法二：数学演绎法

事实上 G(n) 函数的值被称为卡塔兰数 C_n，卡塔兰数更便于计算的定义如下:

h(n)=h(n-1)*(4*n-2)/(n+1);

或者

h(n)=C(2n,n)/(n+1) (n=0,1,2,...)

代码：

1. 代码一：动态规划


/** * code96 */
import java.util.*;

public class code96 {

    public static int numTrees(int n) {
        int G[] = new int[n + 1];
        G[0] = 1;
        G[1] = 1;

        for (int i = 2; i <= n; i++) {
            for (int j = 1; j <= i; j++) {
                G[i] += G[j - 1] * G[i - j];
            }
        }
        return G[n];
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNextInt()) {
            int n = sc.nextInt();
            int ans = numTrees(n);
            System.out.println(ans);
            System.out.println("请继续输入：");
        }
    }
}

2. 代码二：数学演绎法


/** * code96 */
import java.util.*;

public class code96 {

    public static int numTrees(int n) {
        // Note: we should use long here instead of int, otherwise overflow
        long C = 1;
        for (long i = 1; i <= n; i++) {
            C = C * (4 * i - 2) / (i + 1);
        }
        return (int) C;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNextInt()) {
            int n = sc.nextInt();
            int ans = numTrees(n);
            System.out.println(ans);
            System.out.println("请继续输入：");
        }
    }
}

96. 不同的二叉搜索树

题目：

题解：

1. 方法一：动态规划

2. 方法二：数学演绎法

代码：

1. 代码一：动态规划

2. 代码二：数学演绎法

参考：