Given n, how many structurally unique BST's (binary search trees) that store values 1 ... n?
Input: 3 Output: 5 Explanation: 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个节点，可形成多少种不同的BST
思路：
如果数组为空，毫无疑问，只有一种BST，即空树， f(0) =1。
如果数组仅有一个元素{1}，只有一种BST，单个节点， f(1) =1。
如果数组有两个元素{1,2}， 那么有如下2种可能, f(2)=2。
1 2 \ / 2 1
如果数组有三个元素{1,2,3}， 那么有如下5种可能, f(3)=5。
1 1 2 3 3 \ \ / \ / / 3 2 1 3 2 1 / \ / \ 2 3 1 2由此得出规律，
对于任意以i为根节点的二叉树，
其左子树的值一定小于i，也就是[0, i - 1]区间，
而右子树的值一定大于i，也就是[i + 1, n]区间。
假设左子树有m种排列方式，而右子树有n种，则对于i为根节点的二叉树总的排列方式就是m x n
f(2) = f(0) * f(1) + f(1) * f(0);f(3) = f(0) * f(2) + f(1) * f(1) + f(2) * f(0);f(4) = f(0) * f(3) + f(1) * f(2) + f(2) * f(1) + f(3) * f(0);....f(n) = f(0) * f(n-1) + f(1) * f(n-2) + ... + f(n-2) * f(1) + f(n-1) * f(0); 【卡特兰数(Catalan)】
代码：
1 class Solution { 2 public int numTrees(int n) { 3 if(n < 1) return 0; 4 int[] dp = new int[n+1]; 5 dp[0] = 1; 6 dp[1] = 1; 7 for(int i = 2; i <= n; i++){ 8 for(int j = 0; j < i; j++){ 9 dp[i] += dp[j] * dp[i - j - 1]; 10 } 11 } 12 return dp[n]; 13 } 14 }
转载于:https://www.cnblogs.com/liuliu5151/p/9108838.html
相关资源：数据结构—成绩单生成器