--- title: "Dynamic Programming on Two Sequences" description: "Longest common subsequence and edit distance both fill a grid where each cell asks one question about the last character of each string. The table gives the answer, and walking back through it gives t" canonical: https://lightmysky.com/learn/computing/dynamic-programming-on-two-sequences-mt_uNUgHcKKQN source: https://lightmysky.com/learn/computing/dynamic-programming-on-two-sequences-mt_uNUgHcKKQN.md retrieved: 2026-11-12 --- > **Agent view.** This is the Markdown twin of the page, for tools and assistants. > When to use this site, and the call that answers each job: https://lightmysky.com/agent-instructions.md > API description (OpenAPI 3.1): https://lightmysky.com/openapi.json · Authentication: https://lightmysky.com/auth.md > Pricing: https://lightmysky.com/pricing.md · Catalog: https://lightmysky.com/llms.txt · Full catalog: https://lightmysky.com/llms-full.txt > Every machine-readable file on this domain: https://lightmysky.com/.well-known/ai-catalog.json > Ask for Markdown with `Accept: text/markdown`, a `.md` address, or `?mode=agent`. # Dynamic Programming on Two Sequences Longest common subsequence and edit distance both fill a grid where each cell asks one question about the last character of each string. The table gives the answer, and walking back through it gives the alignment that produced it. Subject: Computing · Area: Algorithms & Data Structures · Ages 20 to 21 Page: https://lightmysky.com/learn/computing/dynamic-programming-on-two-sequences-mt_uNUgHcKKQN ## Ready when they can - Fill an edit distance table for two short words and read the answer off the corner - Trace back through the table to recover the actual edits - Explain deletion, insertion and diagonal pairing in the edit-distance recurrence, and distinguish its minimum from the LCS maximum ## Lesson: Filling the grid between two strings As in earlier dynamic programming, first name the subproblem. Put source string S down the rows and target string T across the columns. D(i,j) is the minimum edit cost from the first i source characters to the first j target characters. Row 0 and column 0 represent empty prefixes. For lengths m and n, D(m,n) answers the full problem. Use unit costs: insertion, deletion and substitution each cost 1; matching characters costs 0. Initialize D(i,0)=i because removing i characters takes i deletions. Initialize D(0,j)=j because building j characters from empty takes j insertions. D(0,0)=0. The displayed cells show the start of row 0. For i,j above 0, compare three costs. Delete the last source character: D(i-1,j)+1. Insert the last target character: D(i,j-1)+1. Pair the last characters: D(i-1,j-1)+a, where a is 0 for a match and 1 for a substitution. D(i,j) is their minimum. Fill from shorter prefixes so these neighbors are already known. **Example.** For MAP to MOP, rows use empty, M, MA, MAP and columns use empty, M, MO, MOP. The displayed row lists give the completed table. Its final entry is 1. A traceback pairs M with M, substitutes O for A, and pairs P with P. Only the substitution has a cost. *(drawing: Each cell lists one table row. Within each row, columns are empty, M, MO and MOP.)* Trace back from D(m,n). Move only to a predecessor whose value plus its move cost equals the current value. Up records a deletion, left an insertion, and diagonal a match or substitution. Reverse the recorded moves to perform them from the start. Tied predecessors can give different edit sequences with the same minimum cost. Longest common subsequence, or LCS, keeps character order but allows gaps. L(i,j) is the longest shared subsequence length for the two prefixes. Empty-prefix values are 0. Matching last characters give L(i-1,j-1)+1. On a mismatch use max(L(i-1,j),L(i,j-1)). For AX and AY the length is 1, from A. LCS maximizes length; edit distance minimizes cost. To recover an LCS, start at L(m,n). When the last characters match, record that character and move diagonally. Otherwise move up or left to a cell with the same value as the current cell. A tie allows either move. Stop when a prefix is empty, then reverse the recorded characters. For AX and AY, skip X and Y, then record the matching A. **Recap.** Define prefix states and boundaries. Minimize edit costs or maximize LCS length. Trace back through transitions that preserve the final value. *Original lesson, questions, worked solutions and flashcards written for this dataset.* ## Practice 8 questions on this page, each with its working shown. ## Needs first - [Dynamic Programming: Optimal Substructure and Overlapping Subproblems](https://lightmysky.com/learn/computing/dynamic-programming-optimal-substructure-and-overlapping-subproblems-mt__hWkCDnzNY) ## Optional connections - [Strings: Indexing, Slicing and Length](https://lightmysky.com/learn/computing/strings-indexing-slicing-and-length-mt_33hA050_Qz) ## Opens up - [Alignment Scoring: Substitution Matrices, Gap Penalties and Significance](https://lightmysky.com/learn/science/alignment-scoring-substitution-matrices-gap-penalties-and-significance-mt_k--A8iF5SC) - [Dynamic Programming with a Capacity: Knapsack](https://lightmysky.com/learn/computing/dynamic-programming-with-a-capacity-knapsack-mt_T5pbU_DpdC)