class Solution {
public:
    int numTrees(int n) {
        int dp[100];
        dp[0] = 1;
        dp[1] = 1;
        dp[2] = 2;
        for(int i=3;i <= n;i++){
            int sum = 0;
            for(int j=0;j <= (i-2)/2;j++){
                sum += dp[j]*dp[i-1-j]*2;
            }
            if(i%2 == 1){
                sum += dp[i/2]*dp[i/2];
            }
            dp[i] = sum;
        }
        return dp[n];
    }
};

_