Given n, how many structurally unique BST's (binary search trees) that store values 1 ... n?
Example:
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 个节点组成不同的二叉树个数
Cn 表示有 n 个节点组成不同构二叉树的方案数。下图中，n 等于3，圆形表示节点，月牙形表示什么都没有。
在本题中，n 为 BST 节点个数，则
当 n = 0 时，其 Unique Binary Search Trees 有 1 种，因为空树也算是一种二叉树。
当 n = 1 时，可以看作是其左子树个数乘以右子树个数，此时左右子树都是空树，即均为 1 种，则其 Unique Binary Search Trees 有 种。
当 n = 2 时，由于 1 和 2 都可以为根，所以当 1 为根时，有 种；同理当 2 为根时，有
种；因此总共有
种, 形式化的公式为：
dp[0]*dp[1] 表示1 为 根，根据 BST 的性质，此时左子树为空树；dp[1][0]表示 2 为根，根据 BST 的性质，此时右子树为空树)
当 n = 3时，递推可以得到为 5 种,即
根据以上的关系，利用 DP 方法可解：
class Solution {
public:
int numTrees(int n) {
vector<int> dp(n+1, 0);
dp[0] = 1;
dp[1] = 1;
for(int i = 2; i <= n; i++){
for(int j = 0; j < i; j++){
dp[i] += dp[j] * dp[i-j-1];
}
}
return dp[n];
}
};
