Problem link:- https://practice.geeksforgeeks.org/problems/find-number-of-times-a-string-occurs-as-a-subsequence/0↵
↵
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 memoiszation on this given recursive problem?
↵
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 memoi
