Number Of Binary Tree Topologies

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

using namespace std;

int helper(vector<int>& dp, int n) {
    if(dp[n] != -1) return dp[n];
    dp[n] = 0;
    for(int i = 0; i <= n - 1; i++)
        dp[n] += helper(dp,i) * helper(dp, n - 1 - i);
    return dp[n];
}

int numberOfBinaryTreeTopologies(int n) {
    vector<int> dp(n + 1, -1);
		dp[0] = dp[1] = 1;
    return helper(dp, n);
}