Unique Binary Search Trees
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
推导出递推公式即可：
对于1个元素来说，f[1]=1;
对于2个元素来说，有两种f[2]=2;
对于3个元素来说，
1） 把1作为根节点，则2，3都连在右边，共有2种
2）把2作为根节点，则1，2必须一个在左边，一个在右边，共1种
3）把3作为根节点，则2，3必须在左边，共有2种
把i作为根节点时，我们有前面i-1个元素放在左边，后面i+1到n个元素放在右边
所以对于f[n]我们有以下的公式：
f[n]=f[n-1]+f[1]f[n-2]+f[2]f[n-3]+......+f[n-2]f[1]+f[n-1];
引入f[0]=1,f[1]=1;
则f[n]=f[0]f[n-1]+f[1]f[n-2]+f[2]f[n-3]+......+f[n-2]f[1]+f[n-1]f[0];
class Solution {
public:
int numTrees(int n) {
if(n==||n==)
{
return ;
}
vector<int> f(n+);
f[]=;
f[]=;
for(int i=;i<=n;i++)
{
f[i]=;
for(int j=;j<i;j++)
{
f[i]+=f[j]*f[i-j-];
}
}
return f[n];
}
};