Doubt regarding the acceptance of two similar solutions.
Anonymous User
39
MemoizationDynamic ProgrammingCareer

I was doing a question and I successfully figured out the correct working code of recursion for the question but when I tried to convert it dp using memoization it failed on several large size test cases. And it happens often with me during memoization phase.
can anybody tell me the proper reason and what can I do to avoid this in future.

for example this was the question no. 96 (Unique Binary search Trees):-

my code (passed 12/19 cases):-

int dp[20];

int numTrees(int n) {
memset(dp,-1,sizeof(dp));
    return solver(n);
}

int solver(int n){
    if(n<=1)
        return 1;
    if(dp[n]!=-1)
        return dp[n];
    int ans=0;
    for(int i=1;i<=n;i++){
        
        int left=i-1;
        int right=n-i;
        
      ans=ans+numTrees(left)*numTrees(right);
        
    }
 return dp[n]=ans;
}

The other code that gets accepted without any issue:-

int dp[20]{};
int numTrees(int n) {
if(n<=1)
        return 1;
    if(dp[n])
        return dp[n];
    for(int i=1;i<=n;i++)
        dp[n]=dp[n]+numTrees(i-1)*numTrees(n-i);
 return dp[n];
}
Comments (0)