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

1.简述：

描述

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

数据范围： 

输入描述：

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

输出描述：

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

示例1

输入：

3

输出：

5

示例2

输入：

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