How to approach this question and what is the logic behind this code..https://ide.codingblocks.com/s/160573?_ga=2.185172335.750611047.1610889483-1736087129.1598709607

#1

I found this code on the internet but I’m not able to understand the logic and process…

#2

#include #include #include #include using namespace std; int dp[2001][2001][6]; int N,M; int LCS(long* a,long* b,int n,int m,int k) { if(n==N||m==M) return 0; if(dp[n][m][k]!=-1) return dp[n][m][k]; int res=0; if(a[n]==b[m]) res=1+LCS(a,b,n+1,m+1,k); else { if(k>0) res=1+LCS(a,b,n+1,m+1,k-1); res=max(res,LCS(a,b,n,m+1,k)); res=max(res,LCS(a,b,n+1,m,k)); } return dp[n][m][k]=res; } int main() { int k; cin>>N>>M>>k; long a[N],b[M]; for(int i=0;i<N;i++) cin>>a[i]; for(int i=0;i<M;i++) cin>>b[i]; for(int i=0;i<=2000;i++) for(int j=0;j<=2000;j++) for(int k=0;k<=5;k++) dp[i][j][k]=-1; cout<<LCS(a,b,0,0,k); return 0; }

#3

Hello @abhi542136 have you done the simple lowest common sequence problem?
and have you seen the editorial for both lcs and k ordered lcs?
please confirm this.

#4

Yes, I have solved the simple LCS problem… and I have watched the lecture also. can you send me the link of the editorial of k ordered LCS? or can you simply tell me the logic of k ordered lcs ?

#5

@abhi542136 suppose we have s1and s2 as string and k.
i=0 (for string s1)
j=0(for string s2)

if s1[i]==s2[j]
then ans=1+solvefor(i+1,j+1,k)
if(s1[i]!=s2[j] (we have two options)

ans=solvefor(i+1,j,k) or solvefor(i,j+1,k) take maximum among them // we did similar thing in lcs
if k>0 then i can use 1 k to make them equal and lcs in that case will be
ans=1+solvefor(i+1,j+1,k-1) // k-1 because i have used 1 k to make them equal

among those two options whichever will give maximum answe we will consider that.

for optimisation use 3d dp table:
Here for your reference i am attaching the code:


if you have any doubt you can ask here:
Happy Learning!!

#6

Ok, Thank you… Now it’s fine. :sweat_smile:

#7

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.