Description:
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.
Example:
1 3 3 2 1
\ / / / \ \
3 2 1 1 3 2
/ / \ \
2 1 2 3
Link:
https://leetcode.com/problems/unique-binary-search-trees/description/
解题方法：
初看到这道题，一点头绪都没有，但是在纸上画出n = 0, 1, 2, 3, 4情况以后，才意识到这是道动态规划的题。
如果当n = 0时，只有一种情况就是空树；
当n = 1时，也只有一种情况；
1
当n = 2时，有两种情况：
1 2
\ /
2 1
当n = 3时，其实已经可以看出规律，每当加上一个最大节点，根据这个最大节点和之前节点所构成的树无非是以下这一种形状：
部分之前节点（节点个数可能为0，1，2个）
\
\
当前最大节点（3）
/
/
部分之前节点（节点个数可能为0，1，2个）
当最大节点确定时，只会有以上这种构造情况，由此，根据当前最大节点上面有多少个节点和下面有多少个节点，可以推出动态规划的方程：
dp[i] = dp[0] * dp[i - 1 - 0] + dp[1] * dp[i - 1 - 1] + ... + dp[j] * dp[i - 1 - j] + dp[i - 1] * dp[0]
Time Complexity：
O(N^2)
完整代码：
int numTrees(int n)
{
vector<int> dp(n + 1, 0);
dp[0] = 1;
for(int i = 1; i <= n; i++)
{
for(int j = 0; j < i; j++)
dp[i] += dp[j] * dp[i - j - 1];
}
return dp[n];
}
