VIKRAM91's blog

How to do memoisation on this recursive code?
By VIKRAM91, history, 8 years ago, In English

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 algorithm?

  • Vote: I like it
  • -9
  • Vote: I do not like it

Comments Comments (1)
| Write comment?
»
8 years ago, hide # |
← Rev. 6  
Vote: I like it +7 Vote: I do not like it

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.

→ Reply