the longest common subsequence

A subsequence of a string is what you get by deleting some of its characters (possibly none) without reordering the rest — so 'ace' is a subsequence of 'abcde', but 'aec' is not, because order must be preserved. The longest common subsequence of two strings is the longest string that is a subsequence of both. It measures how much two sequences share in the same order, which is why it underlies diff tools that compare file versions, spell-check suggestions, and even DNA comparison in biology.

The DP rests on looking at the last characters. Let dp[i][j] be the length of the LCS of the first i characters of string A and the first j characters of string B. If A[i] equals B[j], those matching last characters can both be used, so dp[i][j] = 1 + dp[i-1][j-1] — extend the best alignment of the shorter prefixes by this shared letter. If they differ, the last characters cannot both be in the common subsequence, so at least one must be dropped, giving dp[i][j] = max( dp[i-1][j], dp[i][j-1] ) — the better of ignoring A's last char or ignoring B's. The base cases are dp[i][0] = 0 and dp[0][j] = 0, since anything compared with the empty string shares nothing. Filling the (m+1)-by-(n+1) table row by row takes O(mn) time and O(mn) space.

The proof that this is correct is a tidy cut-and-paste: when A[i] = B[j], any optimal common subsequence can be assumed to end with that shared letter (if it did not, you could append it and get something longer or equal), and removing it leaves an optimal LCS of the shorter prefixes — that is optimal substructure. To recover the actual subsequence, not just its length, trace back from dp[m][n]: on a diagonal match step, prepend that character and move to (i-1, j-1); otherwise move toward whichever neighbour gave the max. A useful contrast: a common subsequence allows gaps, whereas a common substring must be contiguous — they are different problems with different DPs, and confusing them is a frequent slip.