Longest Common Subsequence

## How Longest Common Subsequence Works

LCS finds the longest subsequence common to two sequences. A subsequence is a sequence that can be derived by deleting some elements without changing the order.

### Algorithm Steps:
1. Create a DP table of size (m+1) x (n+1)
2. For each cell (i, j):
- If characters match: dp[i][j] = dp[i-1][j-1] + 1
- If not: dp[i][j] = max(dp[i-1][j], dp[i][j-1])
3. Backtrack from dp[m][n] to find the actual LCS

### Key Characteristics:
- **2D DP Table**: Stores solutions to subproblems
- **Backtracking**: Reconstruct solution from the table
- **Applications**: Diff tools, DNA sequence alignment, version control