Longest Common Subsequence
Domain: Algorithms
🎯 Motivation
Find the longest sequence that appears in both strings (not necessarily contiguous). Classic DP problem.
📋 Concrete Example
LCS of ABCD and ACBD is ABD (length 3) or ACD (length 3). The subsequence does not need to be contiguous, just in order.
🔗 Analogy
Finding common scenes between two movie plots. The scenes do not need to be back-to-back, just in the same order in both movies. The longest such chain is the LCS.