The Longest Common Subsequence (LCS) is the longest sequence that appears in the same relative order in two strings but not necessarily consecutively. For example, the LCS of ABCD and ACBAD is ABD. LCS can be solved using dynamic programming by creating a 2D table, where dp[i][j] represents the LCS of the first i characters of one string and the first j of the other. The formula is:
if str1[i-1] == str2[j-1]: dp[i][j] = dp[i-1][j-1] + 1
else: dp[i][j] = max(dp[i-1][j], dp[i][j-1])
It is widely used in file comparison and DNA analysis.