[C++][Unique Binary Search Trees II] simple iterative


#1

Time Complexity: O(A^2)
Space Complexity: O(A)

int Solution::numTrees(int A) {
    vector<int> dp(A+1);
    dp[0] = 1;
    dp[1] = 1;
    for(int i=2; i<=A; i++) 
        for(int j=0; j<i; j++)
            dp[i] += dp[j]*dp[i-j-1];
    return dp[A];
}

Approach:
There can be ‘A’ root nodes, from 1 to A.
For each root node, compute subProblem for left and right.
Ex:
A = 4
root is 1 : 0 left nodes and 3 right nodes
root is 2 : 1 left node and 2 right nodes
root is 3 : 2 left nodes and 1 right node
root is 4 : 3 left nodes and 0 right nodes