---
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-09-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
- Say what each of the three choices in the recurrence corresponds to

## Lesson: Filling the grid between two strings

Longest common subsequence and edit distance both fill a grid. Each row steps through one string and each column through the other. Every cell asks one question about the last character of each prefix.

Each cell picks the cheapest of three moves. Match or substitute pairs the two last characters. Delete skips one from the side string. Insert skips one from the top string.

**Example.** Turn CAT into CUT. The corner of the table reads 1. The traceback pairs C with C, swaps A for U, and pairs T with T. One substitution is the whole answer.

**Tip.** Read the answer off the far corner, then walk back to recover the edits. Each step back names the move its cell chose.

**Recap.** Fill the grid with three choices per cell, read the corner, and trace back the edits.

## 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)
- [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)