题解 | #有多少个不同的二叉搜索树#

import java.util.Scanner;

/**
 * 设dp(n)表示有n个结点时搜索二叉树有多少种可能，则
 *
 * Ⅰ.当头结点的值为1时，左子树为空，右子树上有n - 1个结点，右子树的搜索二叉树个数为dp(n - 1)
 * ...
 * Ⅱ.当头结点的值为i(1 < i < n)时，左子树由结点1—>i-1构成，右子树由结点i+1—>n构成；左子树的搜索二叉树个数为dp(i-1),右子树的搜索二叉树个数为dp(n - i);此时搜索二叉树总的个数为dp(i - 1) * dp(n - i)
 * ...
 * Ⅲ.当头结点的值为n时，右子树为空，左子树上有n - 1个结点，左子树的搜索二叉树个数为dp(n - 1)
 * 
 * 所以，n个结点时搜索二叉树的个数上述三个步骤的和。
 * 
 * 递推公式：
 */
public class Main {


    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String line = scanner.nextLine();
        int n = Integer.parseInt(line);
        System.out.println(numTrees(n));


    }

    public static int numTrees(int n) {
        int[] dp = new int[n + 1];//0个节点的子树也是一种情况，所以有n+1个
        dp[0] = 1;
        dp[1] = 1;
        for (int i = 2; i <= n; i++) {
            for (int j = 0; j < i; j++) {
                dp[i] += dp[j] * dp[i - j - 1];
            }
        }
        return dp[n];
    }
}