Longest Common Subsequence
Explore the problem of finding the longest common subsequence (LCS) between two sequences using dynamic programming. Understand the recurrence relation, optimize the naive exponential approach, and implement a solution with O(m·n) time complexity. This lesson helps you apply tabulation and memoization techniques to solve LCS efficiently.
We'll cover the following...
We'll cover the following...
Problem statement
Given two sequences, find the length of the longest subsequence present in both of them.
A subsequence is a sequence that appears in the same relative order but is not necessarily contiguous.
For example, abc, abg, bdf, aeg, acefg…etc., are subsequences of abcdefg. So a string of length n has different possible subsequences.
Solution: Naïve method
Let ...