I am trying to solve SAMER08D  DNA Sequences . I know how to solve LCS but can't figure out how to think of states in this problem. I tried reading approaches for the solution of this problem on google but I only got codes. However, that didn't help as I did not get a feel what code was trying to do. Can you please help me with this ? asked 08 Jan '17, 09:41

The standard LCS problem is solved with the help of this function definition and the application of dynamic programming. You can find the code in this geeksforgeeks article, I think the explanation is quite clear. If you understand how this works we can now attempt to solve the SAMER08D problem. The only difference between the standard problem and the modified version is that the number of common characters we take at a time has a lower bound, which is the value k. We must always take k or more common characters to add the subsequence we will be building via dp. So the statement for(i=0; i<=xlen; i++){ for(j=0; j<=ylen; j++){ dp[i][j] = 0; if(i==0  j==0) continue; c = 1; while(ic>=0 && jc>=0 && x[ic]==y[jc]){ if(c>=k) dp[i][j] = MAX(dp[i][j], c+dp[ic][jc]); c++; } dp[i][j] = MAX(dp[i][j], dp[i1][j]); dp[i][j] = MAX(dp[i][j], dp[i][j1]); } } Complete solution here. answered 09 Jan '17, 00:38

Still waiting...