Longest Common Subsequence

#1

I did not understood the line

dp[i][j] = max(dp[i-1][j], dp[i][j-1])

#2

hello @dare_devil_007

if s1[i]!=s2[j] then we have two case
case 1 -> compute lcs of string s1[0,i-1] and s2[0,j]
case 2- > compute lcs of string s1[0,i] and s2[0,j-1]

and we need to pick maximum of these two case.

this line is for the same.

refer this article for more detail

#3

Consider the input strings “ABCDGH” and “AEDFHR. Last characters do not match for the strings. So length of LCS can be written as:
L(“ABCDGH”, “AEDFHR”) = MAX ( L(“ABCDG”, “AEDFH R ”), L(“ABCDG H ”, “AEDFH”) )

this is where i am getting stuck. i am not able to understand how this thing works
can you please explain me?

If it does not matches we can have the LCS like dp[i][j] = dp[i-1][j-1] right?

#4

no either we discard ith character of 1st string or , jth character of second string.

#5

if the characters doesn’t match the LCS won’t change right and so it has to be the value till i-1 and j-1 right.

#6

abck
xabc
here if u see k and c are not equal , so if u ignore both then abc,xab can give u at max 2 length lcs, but correct answer is 3 (abc) .
that is reason why we dont discard both.
either we discard i or j , and which will give max we will consider that

1 Like
#7

Okay!! thanks a lot for your guidance mate!!