题目描述 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的数目，可以由之前的数算出来
例如n = 5；我们可以假设 1作为root，那么左边没有数，右边有4个数，4个数可以组成情况数目，之前已经存起来了。
以此，2作为root，累加可得。
代码：
class Solution {
public:
int numTrees(int n) {
int *p = (int*)malloc(sizeof(int) * (n+1));
p[0] = 1;
if(n == 0)
return 0;
else
{
for(int i = 0;i < n;i ++)
{
p[i+1] = 0;
for(int j = 0;j <= i;j ++)
p[i+1] = p[i+1] + (p[j]*p[i-j]);
}
}
return p[n];
}
};
