Think recursive...optimise it...u r done


#1

vector<vector> dp;
int ans(int s,int e){

int ve=0;
if(s==e)return 1;
if(s>e)return 1;
if(dp[s][e]!=0)return dp[s][e];
for(int i=s;i<=e;i++){
   ve+= ans(s,i-1)*ans(i+1,e);
}
return dp[s][e]=ve;

}

int Solution::numTrees(int A) {
dp.clear();
dp.resize(A+1,vector(A+1,0));
return ans(1,A);

}