Unique Binary Search Trees
给一个数字, 问能组成多少个唯一的BST. 卡特兰数
1 2 3 4 5 6 7 8 9 10 11 12 13 |
public class Solution { public int numTrees(int n) { int[] dp = new int[n+1]; dp[0] = dp[1] = 1; for(int i = 2; i<=n; i++) { for(int j = 1; j <= i; j++) dp[i] += dp[j-1] *dp[i-j]; } return dp[n]; } } |