How to do memoisation on this recursive code?

Revision en2, by VIKRAM91, 2018-04-25 14:26:11

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 memoization on this given recursive problem?

Tags #dp, #recursion

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en3 English VIKRAM91 2018-04-25 14:50:19 12 Tiny change: 'recursive problem?' -> 'recursive algorithm?'
en2 English VIKRAM91 2018-04-25 14:26:11 105
en1 English VIKRAM91 2018-04-25 14:24:20 801 Initial revision (published)