VIKRAM91's blog

By VIKRAM91, history, 4 weeks 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  

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by VIKRAM91 (previous revision, new revision, compare).

»
4 weeks ago, # |
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.

  • »
    »
    4 weeks ago, # ^ |
    Rev. 4   Vote: I like it 0 Vote: I do not like it

    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);
    }