1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution {
public:
    int numTrees(int n) {
        // Note: The Solution object is instantiated only once and is reused by each test case.
        if(n == 1)return 1;
        if(n == 2)return 2;
        if(n == 3)return 5;
        int *num = new int[n + 1];
        num[0] = 1;
        num[1] = 1;
        num[2] = 2;
        num[3] = 5;
        for(int i = 4;i <= n;i++)
        {
            num[i] = 0;
            for(int j = 1;j <= i;j++)
            {
                num[i] += num[j-1]*num[i-j];
            }
        }
        return num[n];
    }
};