Problem Link : https://www.interviewbit.com/problems/longest-common-subsequence/

Can anyone help me out.

why this code is giving time limit error(tle):

int fun(vector<vector > &dp,int i,int j,string s1,string s2) { if(i==s1.length()|| j==s2.length()) return 0; int &ans=dp[i][j]; if(ans!=-1) return ans; ans=max(fun(dp,i,j+1,s1,s2),fun(dp,i+1,j,s1,s2)); if(s1[i]==s2[j]) ans=max(ans,1+fun(dp,i+1,j+1,s1,s2)); return ans; }

int Solution::solve(string s1, string s2) { if(!s1.length() || !s2.length()) return 0; int n=s1.size(),m=s2.size(); vector<vector > dp(n,vector (m,-1)); return fun(dp,0,0,s1,s2); }

and why this code get accepted:

× int Solution::solve(string s1, string s2) { if(!s1.length() || !s2.length()) return 0; int n=s1.size(),m=s2.size(),i,j; vector<vector > dp(n+1,vector (m+1,0)); for(i=1;i<=n;i++) for(j=1;j<=m;j++) { if(s1[i-1]==s2[j-1]) dp[i][j]=1+dp[i-1][j-1]; else dp[i][j]=max(dp[i-1][j],dp[i][j-1]); } return dp[n][m]; }

both solutions have time complexity O(m*n) memoization gives tle and tabulation passes the constraints why?? Thanks in advance.