CODEWITHSUNDEEP
algorithmdynamic-programminglcs
Einsambr
Einsambr

Reputation: 189

How to use DP to solve "Longest similar subsequence"

I've read the solutions to the LCS problem. But now there's a Longest Similar Subsequence problem: A sequence C is a similar subsequence of two sequences A, B if and only if C is a subsequence of A and we can replace at most K elements in C such that C is a subsequence of B.

For example, if A = "ABCDE", B = "BCAFE", K = 1, then the longest similar subsequence is "BCDE" ("BCDE is a subsequence of "ABCDE", and we can replace 'D' with 'A' or 'F' to make it a subsequence of "BCAFE").

My problem is that I've only come up with a recursive method to solve it, but obviously this is time-consuming, so I want to use DP instead. Any idea how to use DP to solve this problem?

My recursion method is like this:

LSS(i, j, k)
    if(i == 0 or j == 0)
        return 0
    if(A[i] == B[j])
        return LSS(i-1, j-1, k) + 1
    if(k > 0)
        return max(LSS(i-1, j-1, k-1) + 1, LSS(i-1, j, k), LSS(i, j-1, k))
    else
        return max(LSS(i-1, j, k), LSS(i, j-1, k))

Upvotes: 0

Views: 388

Answers (1)

user2736738
user2736738

Reputation: 30906

DP is all about understanding the optimal sub-problem and then use it in getting other solution. Without all that details we can simply use the idea that comes automatically.

Here what we are doing is simply computing the same solution over and over. That's why the solution is much more time consuming. What you can do is memoize the solution.

So in this case intialize sol with -1. Then before getting the solution of LSS(i,j,k) you can check whether sol[i][j][k] is already computed. If it is then just use it otherwise solve the solution and put it in sol. Standarrd memoization.

Upvotes: 1

Related Questions