LintCode链接
给出 n，问由 1...n 为节点组成的不同的二叉查找树有多少种？
您在真实的面试中是否遇到过这个题？ Yes 样例给出n = 3，有5种不同形态的二叉查找树：
1 3 3 2 1 \ / / / \ \ 3 2 1 1 3 2 / / \ \ 2 1 2 3 标签 卡特兰数 动态规划 public class Solution { /** * @paramn n: An integer * @return: An integer */ public int numTrees(int n) { int[] dp = new int[n+1]; dp[0]=1; return helper(dp, n); } //方法一 //记忆+递归 public int helper(int[] dp, int n) { if(dp[n]>0) return dp[n]; //每个node做root情况下的种数 for(int i=1; i<=n; i++){ dp[i-1] = dp[i-1]>0?dp[i-1]:helper(dp, i-1); dp[n-i]= dp[n-i]>0?dp[n-i]:helper(dp, n-i); dp[n] += dp[i-1]*dp[n-i]; } return dp[n]; } //方法二 //AC=95% //超时 public int helper_1(int n) { if(n==0) return 1; int res=0; //每个node做root情况下的种数 for(int i=1; i<=n; i++){ int left=helper_1(i-1); int right=helper_1(n-i); res += left*right; } return res; } }