Unique Binary Search Trees II

• Time : $O(n^2)$
• Space : $O(n)$

c++

int dp[20];
int helper(int n) {
    if(n <= 1) return 1;
    if(dp[n]) return dp[n];
    int& res = dp[n];
    for(int i = 1; i <= n; i++) {
        res += helper(i - 1) * helper(n - i);
    }
    return res;
}
int Solution::numTrees(int A) {
    return helper(A);
}