lc96-Unique Binary Search Trees

發表於   |   分類於   |   0 comments   |   
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    int max = 0;
    vector<int> F;
    int numTrees(int n) {
        if (n > max) {
            for (int i = 0; i < n + 1 - max; i++)
                F.push_back(-1);
            max = n;
            
        }
        if (n == 0 || n == 1) {
            F[n] = 1;
            return 1;
        }
        else {
            if (F[n] != -1) return F[n];
            F[n] = 0;
            for (int i = 0; i < n; i++)
                F[n] += numTrees(i)*numTrees(n-1-i);
            return F[n];
        }
    }
};