96. Unique Binary Search Trees

1.問題

• 給一個n, 計算有多少BST組合

2.想法

• When the number of nodes is 1 there is just one possible tree- this is the base case

• Consider that every node can be the root - the nodes before it will be on the left and the nodes after it on the right

3.程式碼

class Solution {
public:
    int numTrees(int n) {
        vector<int> v(n + 1, -1);
        return numTreesCount(n, v);
    }
private:
    int numTreesCount(int n, vector<int>& v) {
        if (n == 0 || n == 1) {
            return 1;
        }
        if (v[n] != -1) {
            return v[n]; 
        }
        
        int sum = 0;
        for (int i = 1; i <= n; i++) {
            int left = numTreesCount(i - 1, v);
            int right = numTreesCount(n - i, v);
            sum = sum + left * right;
        }
        v[n] = sum;
        return sum;
    }
};

4.Performance