动态规划 dp -- 题解 P2758 【编辑距离】

jijidawang · 2020-03-22 17:55:17 · 题解

题面简述

编辑距离 ——经典 dp 问题

设 s_1 和 s_2 是两个字符串。我们要用最少的字符操作次数，将字符串 s_1 转换为字符串 s_2 。这里所说的字符操作共有三种：

1. 删除一个字符；

2. 插入一个字符；

3. 将一个字符改为另一个字符；

算法分析

暴力算法

我们当然可以写个 bfs 求解。

果然很暴力。

dp 算法

我们发现，这个操作只更改一个字符，别的字符不受影响，考虑 dp。

由于对于字符串的操作只有 4 种情况（分别是：删除，添加、更改、不变），我们可以从这里下手设计转移方程。

我们可以设 dp_{i,j} 表示将 s_1 的前 i 个字符变为 s_2 的前 j 个字符的编辑距离。

因为它们最后相等了，所以它们的末尾字符肯定也相等。

• 删除操作：我们设删除 s_1 的末尾字符，则为 dp_{i-1,j}，由于此操作需要一步，所以还要 +1。

• 插入操作：假设在 s_1 末尾添加字符，我们想：

插入到最后，就是插入 s_2 的末尾字符，这样就可以转移到 dp_{i,j-1} ，当然还要 +1。

• 替换操作：还是假设更改最后一个字符，改之前它们不相等，所以考虑前面的串的次数即可，即 dp_{i-1,j-1}+1

• 不变的话显然是 dp_{i-1,j-1}（最后本来都相等了，当然就是前面的次数了，不变当然不用耗费次数啦）

求最短次数，求 \min 即可。

整理出转移方程：

提出 1 后：

按照转移方程 dp 即可。

时间复杂度 \mathcal{O}(len_1len_2)（设 s_1,s_2 的长度分别为 len_1,len_2）