Dynamic Programming | Set 4 (Longest Common Subsequence) | GeeksforGeeks

This video is contributed by Kanika Gautam.

[fredb]

I don't understand why all these algorithm videos never explain how to get the solution. It's always something random like "max of top and left cell" without ever explaining what those values are. It's like the people making these videos do not even understand themselves.

[LordShish]

How is anyone supposed to think of this solution themselves?

[fleroviumgaming]

At 6:42 you can use that G. You say "1 came from the left cell" but it didn't. It is 1 because G matches G, and the diagonal was 0. You skip that G for no reason.

[danielalvarado]

I was reading the explanation of how this works but I could not get properly how the table actually gets filled. This video hit the spot. Thanks!

[terigopula]

Please do not forget to mention the time and space complexity of the algorithms that you teach, since it is just as important. Nice explanation by the way :)

[indowestlife]

You just told us what to do, not why you did it.

[HaKazzaz]

*For everyone asking why the matrix is built this way* :
When you are using dynamic programming you need to understand the recursive algorithm you would like to optimize.
I'll explain the non-genius solution where you go letter by letter from the start of each string.
The DP answer will be built bottom-up which would make the table fill from the end of the string as the vid suggests.


In this case (x is L1, y = L2):
LCS = {
1 + LCS(i+1, j+1) ; IF x[i]==y[j]
max(LCS(i+1, j), LCS(i, j+1)) ; ELSE
}
This is the top-down approach.


Now if you would like to convert the recursive solution to a matrix you need to take a bottom-up approach. And so the algorithm will look as follows:
LCS = [N][M] // N = len(x), M = len(y)

if x[i]==y[j]:
LCS[i][j] = 1 + LCS[i-1][j-1]
else:
LCS[i][j] = max(LCS[i-1][j], LCS[i][j-1])
Note that the matrix has to have a initialization row and column where all values are 0 in order to have an answer for i-1 and j-1 in the first run.
So if you are coding you should also use the case:
if (x[i] == 0 || y[j] == 0) -> LCS[i][j] = 0


You can easily see the correlation between the recursive and the DP solutions.
Just keep practicing, it is a skill worth working for and not black magic (as some may feel after watching this video).

[the_ghost_of_uchiha]

The table should be drawn in reverse i.e "AGGTAB" in row wise & "GXTXAYB" in column wise, after that if we wanna print the output by printing the matrix that would be the actual table. Thank you

[gunashaalini]

Very good explanation which is easy to follow and saves a lot of time. Well done Kanika!!!

[radhasingh]

Thank you so much for the short and clear explaination :)

[arpitkesarwani]

superb way of explaining..nd awesome ppt

[yackawaytube]

Calm down. The table explanation is very clear to me. Think about what she said at @1:20, the table is just a way to capture the recursive calculation.

[silongliu]

The video is great! I read a lot of articles do not see how to find out the largest common sub-sequence, but I saw your video, got it...thank you...thank you...thank you

[hailenders]

Thank you for explaining those algorithms so simply! 😀

[likheshmahajan]

@Kanika, The video that you posted is same as DSA - Tabulation from GFG, why repeat?
Expectation from this video was to print the LCS or return a List, I don't see either mentioned in this video.

[asakiran]

at 5:09 LCS[i-1][j] is top cell and LCS[i][j-1] is left cell

[vatsalmankodi]

Excellent explanation! It was very helpful. Thank You.

[thesoftwareengineer]

hey can u please provide the code snippet for this video.along with how to print the longest common sub sequence string

[cpcp]

you explain the procedure but did not explain how you came up with that procedure..
please explain that also so that we can think the algorithm that solve particular problem...

[veerakalyannanubala]

Hello
Can u please explain
why u picked max(leftcell, upcell) when characters dont match
Why we have to increment value of diagonal by 1 when characters match.