#yyds干货盘点# 动态规划专题：有多少个不同的二叉搜索树

1.简述：

给定一个由节点值从 1 到 n 的 n 个节点。请问由多少种不同的方法用这 n 个节点构成互不相同的二叉搜索树。

数据范围： 

仅一行输入一个正整数 n ，表示节点的数量。

输出组成不同二叉搜索树的方法数。

输入：

3

输出：

5

输入：

2

输出：

2

2.代码实现：

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int nodeNum = scan.nextInt();
        System.out.println(getTotal(nodeNum));
    }
    public static int getTotal(int num){
        if (num <= 1){
            return 1;
        }
        int res = 0;
        for (int i = 1; i <= num; i++) {
            res += getTotal(i - 1) * getTotal(num - i);
        }
        return res;
    }
}