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
一刷
题解：与95. Unique Binary Search Trees II的不同之处在于，求出所有的排列组合数目而不是真正的排列组合。
根据表达式dp[n+1] = sum_{i=0}^n(dp[n-i]*dp[i]),可以得到下题的解：
Time complexity - O(n), space complexity - O(n)
public class Solution {
public int numTrees(int n) {
if(n<0) return 0;
int[] dp = new int[n+1];
dp[0] = 1;//null
for(int i=1; i<=n; i++){//n+1, n = i-1
for(int j=0; j<i; j++){
dp[i] += dp[i-1-j]*dp[j];
}
}
return dp[n];
}
}
