Please subscribe to the official Codeforces channel in Telegram via the link: https://t.me/codeforces_official. ×

VIKRAM91's blog

By VIKRAM91, history, 8 months ago, ,

I have written recursive solution for this problem:-

#include<bits/stdc++.h>
using namespace std;
int cnt=0;
int ans(string s1,string s2,int n,int m){
if(n==0&&m==0||m==0)
return 1;
if(n==0)
return 0;
if(s1[n-1]==s2[m-1]){
return ans(s1,s2,n-1,m-1)+ans(s1,s2,n-1,m);
}
else return ans(s1,s2,n-1,m);
}

int main(){
int t;
cin>>t;
while(t--){
int n,m;
cin>>n>>m;
string s1,s2;
cin>>s1>>s2;
cout<<ans(s1,s2,n,m)<<endl;
}
return 0;
}

How should I approach to do memoization on this given recursive algorithm?

•
• -9
•

 » 8 months ago, # |   0 Auto comment: topic has been updated by VIKRAM91 (previous revision, new revision, compare).
 » 8 months ago, # | ← Rev. 6 →   +7 As I can see from your code, you only change n and m parameters and the result only depends on those parameters. So your function ans is pure. We can create array int calculated_answers[n+1][m+1] and fill it with -1 (or any other special value that never appears as answer) — that means value is not calculated yet.And function ans should be written like this: int ans(string s1,string s2,int n,int m){ if (calculated_answers[n][m] == -1) { if(n==0&&m==0||m==0) calculated_answers[n][m] = 1; else if(n==0) calculated_answers[n][m] = 0; else if(s1[n-1]==s2[m-1]){ calculated_answers[n][m] = ans(s1,s2,n-1,m-1)+ans(s1,s2,n-1,m); } else calculated_answers[n][m] = ans(s1,s2,n-1,m); } return calculated_answers[n][m]; }This will not recalculate already calculated value.Also consider making s1 and s2 global (as you never change them) to avoid passing them into function ans every time.
•  » » 8 months ago, # ^ | ← Rev. 4 →   0 Written your method but got the wrong answer(maybe I implemented wrong), then I wrote This method and got AC. But thanks anyway. int ans(string s1,string s2,int n,int m){ if(n==0&&m==0||m==0) return 1; if(n==0) return 0; if(s1[n-1]==s2[m-1]){ return memo[n][m]=ans(s1,s2,n-1,m-1)+ans(s1,s2,n-1,m); } else return memo[n][m]=ans(s1,s2,n-1,m); }