How to Solve Problems using Dynamic Programming on Strings

String DP problems typically involve two strings and ask you to find the optimal way to compare, transform, or match them. The key insight is that the answer for two strings of length M and N can be built from answers to smaller subproblems involving prefixes of those strings.

For the Longest Common Subsequence problem, define DP at row i and column j as the length of the longest common subsequence between the first i characters of string one and the first j characters of string two. Fill this table bottom up starting from the smallest prefixes.

If the characters at position i in string one and position j in string two are equal, the LCS length is one plus the LCS of the previous prefixes, which is the value diagonally above left. If the characters are different, take the maximum of the value directly above and the value directly to the left, representing the best answer without one of the two current characters.

For Edit Distance, define DP at row i and column j as the minimum number of operations needed to convert the first i characters of string one into the first j characters of string two. The allowed operations are insert, delete, and replace.

If characters match, no operation is needed and the value is the same as the diagonal. If they do not match, take the minimum of three values. The diagonal plus one represents a replacement. The cell above plus one represents a deletion. The cell to the left plus one represents an insertion.

For both problems, the first row and first column represent comparisons with empty strings. For LCS, these are all zero because no common subsequence exists with an empty string. For Edit Distance, the first row values are 0 through N and the first column values are 0 through M, representing the cost of building or destroying characters one by one.

The final answer for both problems sits in the bottom right cell of the table. To reconstruct the actual sequence or sequence of operations, trace back from the bottom right to the top left by reversing the decisions made at each cell. Moving diagonally means a match or replacement, moving up means a deletion, and moving left means an insertion.