96. Unique Binary Search Trees

problem description

Given n, how many structurally unique BST's (binary search trees) that store values 1 ... n?

Example:

Input: 3
Output: 5
Explanation:
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

algorithm thought

和上题一个类型，简化了一点。上一题需要输出所有的结果，这里不需要结果，只需要数字。对于上一题，我们保存一棵树开始和结束的位置。来映射他的结果，但是这里不需要，因为只要树的size固定好，能生成的所有的tree的数量也就出来了。这里使用一个数组保存结果

code

class Solution {
public:
    int numTrees(int n) {
        vector<int> dp(n+1,0);
        dp[0]=1;
        dp[1]=1;
        int left,right;
        for(int i=2;i<=n;++i){
            for(int j=1;j<=i;++j){
                left=j-1;
                right=i-j;
                dp[i]+=dp[left]*dp[right];
            }
        }
        return dp[n];
    }
};

algorithm analysis

算法中有两个循环，执行n²次，每次执行时间复杂度O(n)，最后时间复杂度O(n²)