北京海淀区信息学竞赛 · 2023 北京市海淀区信息学竞赛（初赛）试题 第 10 题

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

这题考编辑距离（Levenshtein），核心是把两个串看成序列，用动态规划算最少插入/删除/修改步数，从空串或末尾开始一步步填表。

学生容易把编辑距离当成汉明距离（只数不同字符），忽略插入和删除；或误以为只要把A里的字符重新排列就能匹配，忘了编辑距离允许增删改，不是简单重排；还有人会逐位比较，没意识到中间可以跳过不匹配的字符。

这道题考查的是编辑距离（Levenshtein distance）这一经典概念，常用于衡量两个字符串的相似度。编辑距离定义为：将字符串A变为B所需的最少操作步数，允许的操作有：删除一个字符、插入一个字符、修改一个字符。命题人喜欢用短串之间看似只需少量改动，但实际最优解需要巧妙跳过或替换的题目来挖坑，比如本题中A和B长度相同，但字符顺序完全不同，容易让人误以为要全部重排。拿到题先想：能不能直接数不同字符？不能，因为编辑距离允许插入和删除，所以即使长度不同也能通过增删匹配。正确思路是动态规划：设dp[i][j]表示A的前i个字符变成B的前j个字符的最小编辑距离。边界：dp[0][j]=j（全部插入），dp[i][0]=i（全部删除）。转移：若A[i]==B[j]，则dp[i][j]=dp[i-1][j-1]；否则dp[i][j]=1+min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])，分别对应删除、插入、修改。按这个递推填表，从i=1到7、j=1到6逐步计算，最终dp[7][6]即为答案。避坑：别把题目看成排序或汉明距离；别认为只要字符集相同就只需重排；别忽略长度变化带来的插入删除成本。历年考频显示，编辑距离在CSP-J/S近五年中每年至少出现一次，2023年海淀区真题再次将其作为单选题，说明它是高频考点，且常与字符串处理结合。未来可能继续以动态规划形式出现，或与哈希、双指针等结合考察更复杂场景。暂无足够依据预测具体新题型，但掌握其DP框架是应对此类题的关键。