How to do memoisation on this recursive code?

Правка en1, от VIKRAM91, 2018-04-25 14:24:20

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

Теги #dp, #recursion

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en3 Английский VIKRAM91 2018-04-25 14:50:19 12 Tiny change: 'recursive problem?' -> 'recursive algorithm?'
en2 Английский VIKRAM91 2018-04-25 14:26:11 105
en1 Английский VIKRAM91 2018-04-25 14:24:20 801 Initial revision (published)