一、原题
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.
1 3 3 2 1
\ / / / \ \
3 2 1 1 3 2
/ / \ \
2 1 2 3
二、题意
给定数字n，求问由1～n的数字所构成的不同二叉搜索树（BST）的数目。
三、思路
先从简单的分析起：
- n = 1：很容易想到结果为1；
- n = 2：很容易想到结果是2；
- n = 3：此时可以考虑成：
- 将数字3插入到数字2的所有BST中，则此时数字3在2的所有BST中的位置都是固定的，也就是将数字3插入到数字2的所有BST后，新生成的树个数等于原来数字2的BST的数目，等于2；
- 将数字3插入到数字1的所有BST中，同理位置也是固定的（1的右子树），但此时有个问题就是2尚未插入到新的二叉树中，则2插入的位置也是固定的，那最终生成的二叉树个数，等于1；
- 最后是3作为根：则考虑将1、2插入到3作为根的BST中，因为3最大，所以1、2插入的位置肯定在3的左子树，就相当于数字2的所有BST作为3的左子树，所以数目等于数字2的BST的数目，等于2；
- 综上：数字3的BST数目为2 + 1 + 2 = 5；
- 尚未能明显总结出规律，继续推断，n = 4：
- 将数字4插入到数字3的BST中，4的插入位置唯一，生成的数量等于3的BST数目，等于5；
- 将数字4插入到数字2的BST中，则4作为右子树，然后再插入数字3，3插入的位置是固定的，又因为2的BST数量为2，所以4的位置有两种，因此该情况生成的BST数目等于2；
- 将数字4插入到数字1的BST中，则4同样作为右子树，此时需要插入数字3和2，此时3和2构成的BST肯定作为4的最字数，所以数量上等于2的BST，等于2；
- 将数字4作为根，所以新生成的BST数量等于数字3的BST数量；
- 综上：数字4的BST数目为5 +２ + 2 + 5 = 14
....
综上，假设要求数目为n的BST数目，dp[i]用来表示数量为i的BST数目：
- n作为根：生成BST数量为等于(n-1)的BST数目：dp[n - 1]；
- n插入到(n-1)的BST中：数量为dp[n - 1]；
- n插入到(n-2)的BST中，则尚未插入的数据还有数字(n-1)，则最终生成的数量为dp[n - 2]
- n插入到(n-3)的BST中，则尚未插入的数据还有数字(n-2)和(n-1)，则最终生成的数量为dp[n - 3] * dp[2]
.... - n插入到(n-i)的BST中，则尚未插入的数据还有数字(n - 1)、(n - 2)、...、(n - i + 1)，因为n插入到(n-i)的BST中，则n都是作为右子树且插入位置唯一，所以新生成的数量等于(n - 1)、(n - 2)、...、(n - i + 1)这几个数字构成的BST的数目，所以生成的数目为：dp[n - i] * dp[i - 1]；
故 $$dp[n] = \sum\limits_{i = 1}^{n - 1} (dp[n - i] * dp[i - 1])$$
四、代码
class Solution {
public:
int numTrees(int n) {
if(n <= 1){
return 1;
}
int *dp = new int[n + 1];
dp[0] = 1;
dp[1] = 1;
for(int i = 2; i <= n; ++i){
dp[i] = dp[i - 1];
for(int j = 1; j < i; ++j){
dp[i] += dp[i - j] * dp[j - 1];
}
}
int res = dp[n];
delete[] dp;
return res;
}
};
