编辑距离

一句话理解

编辑距离：插、删、改，变成另一个串的最少次数。

为什么要学

DP：f[i][j] 前缀变前缀。

讲解

改：对角+1；删：上+1；插：左+1。字符相等对角 +0。

例子

三个操作三个来源取 min。

常见错误

• 代价不是 1 时没改转移。
• 空串边界没设成 i 或 j。