Dp CPP recursive Solution


#1

int recur(int A,vector &dp){

if(!A)return 1;
if(dp[A]!=-1)return dp[A];
int ans=0;
for(int i =1;i<=A;i++){
    int l = recur(i-1,dp);
    int r = recur(A-i,dp);
    ans += l*r;
}
dp[A]=ans;
return ans;

}

int Solution::numTrees(int A) {

vector<int> dp(A+1,-1);
return recur(A,dp);

}