96. Unique Binary Search Trees

Given an integer n, return the number of structurally unique BST’s (binary search trees) which has exactly n nodes of unique values from 1 to n.

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

        return dp[n];
    }
};

class Solution {
    int dp[20];
    int dfs(int n) {
        if(dp[n] != -1) return dp[n];
        dp[n] = 0;
        for(int i = 0; i < n; i ++) {
            dp[n] += dfs(i) * dfs(n - i - 1);
        }
        return dp[n];
    }
public:
    int numTrees(int n) {
        memset(dp, -1, sizeof(dp));
        dp[0] = dp[1] = 1;
        return dfs(n);
    }
};