Given n, how many structurally unique BST's (binary search trees) that store values 1...n?

For example,

Given n = 3, there are a total of 5 unique BST's.

1         3     3      2      1    \       /     /      / \      \     3     2     1      1   3      2    /     /       \                 \   2     1         2                 3 给定一个数字n，返回n个节点一共有多少种二叉搜索树。 思路:一开始我的思路是使用排列组合得出每个二叉搜索树，后来看到题目是可以使用DP。然后查了下，发现应该使用一种卡特兰数的东西。 关于卡特兰数可以看这篇博文:https://www.cnblogs.com/code-painter/p/4417354.html 对于给定的n，我们可以分别求当1、2、3....n为根的时候的搜索二叉树的数目再求和。 当第k个数作为根的时候，左子树有k-1个节点，右子树有n-k个节点。 所以此时的搜索二叉树的数目为dp[k-1]*dp[n-k](dp[i]为当n=i的时候拥有的二叉搜索树的数目) 当n=0的时候dp[0] = 1，因为空树也算是一种二叉树，当只有一个节点的时候dp[1]=1. 当有两个节点的时候分两种情况，以1为根的时候，和以2为根的时候。 dp[2] = dp[0]*dp[1] //当根为1的时候         + dp[1]*dp[0]  //当根为2的时候 当有三个节点的时候分三种情况: dp[3] = dp[0]*dp[2]            //1为根节点 　　　　+dp[1]*dp[1]　　　　　　　　//2为根节点 　　　　+dp[2]*dp[0]　　　　　　　　//3为根节点 实现代码如下:

1 public class Unique_Binary_Search_Trees { 2     public static int numTrees(int n) { 3         if(n==0)    return 0; 4         if(n==1)     return 1; 5          6         int[] result = new int[n+1]; 7         result[0] = 1; 8         result[1] = 1; 9         result[2] = 2;10         11         if(n<3){12             return result[n];13         }14         15         for(int i=3;i<=n;i++){16             for(int k=1;k<=i;k++){17                 result[i] += result[k-1]*result[i-k];18             }19         }20         21         return result[n];22     }23     24     public static void main(String[] args) {25         System.out.println(numTrees(3));26     }27 }