The LCS problem finds the longest sequence that appears in the same relative order in two strings. It is the core algorithm behind Git Diff, File Comparisons, and DNA Sequencing.
If characters match: dp[i][j] = 1 + dp[i-1][j-1].
If they don't: dp[i][j] = Max(dp[i-1][j], dp[i][j-1]).
This builds a matrix from the bottom up, with the final answer sitting at the bottom-right cell.
Q: "How does Git use the LCS algorithm?"
Architect Answer: "Git calculates the LCS of two file versions. Any lines (characters) NOT in the LCS are considered 'Changes' (Additions or Deletions). By finding the longest common part, Git can minimize the 'Noise' in a diff and show the developer exactly what changed as efficiently as possible."