NOIP 普及 2011 第一轮 第 22 题：两个字符串的编辑距离

题目

定义字符串的基本操作为：删除一个字符、插入一个字符和将一个字符修改成另外一个字符这三种操作。将字符串 $A$ 变成字符串 $B$ 的最少操作步数，称为字符串 $A$ 到字符串 $B$ 的编辑距离。字符串 $\texttt{ABCDEFG}$ 到字符串 $\texttt{BADECG}$ 的编辑距离为_。

答案

3

题解

考点定位

本题考「编辑距离」,对应大纲 4.3.2 动态规划（难度【4】）。

解题过程

ABCDEFG → BADECG。DP 或直接构造：

1. 删首字符 A：BCDEFG（1 步）
2. 开头插入 B：BBCDEFG？换思路——目标 BADECG。

构造 3 步：①删 A → BCDEFG；②把 C 改为 A → BADEFG；③删 F → BADECG ✓。

更规范 DP 验证 ≤3；而两串长度 7 与 6，且 B、A、D、E、C、G 的对齐需要至少：A 删、C 改 A、F 删 = 3 步（长度差 1 至少 1 删；公共子序列 BCDEG 长 5，需 7−5=2 删 + 6−5=1 改 = 3）。下界 3 可达。

答案：3。

易错提醒

① 编辑距离 = 1 − LCS 相关式：len(A)+len(B)−2×LCS（纯增删）+ 改写修正；② 找最长公共子序列 BCDEG（长 5）是核心。