# 15-3 编辑距离 ## 题目概述 有六种操作，分别是复制（copy）、替换（replace）、删除（delete）、插入（insert）、交换（twiddle）、消灭（kill）。\ 将这六种操作任意组合（可以重复或者没有）得到一个操作序列。\ 操作序列的输入是一个字符串，操作的输出是另一个字符串。\ 例如字符串algorithm，经过以下操作序列，得到字符串altruistic。\ ![](http://img.my.csdn.net/uploads/201208/30/1346306961_5723.gif)\ 一个字符串src，变成另一个字符串dst，可以很多种方法。\ 题目要求对于给定的src和dst，找到一种最优的操作序列，包含最少的操作个数，使src变成dst。输出这个操作序列。操作序列中操作的个数就是src到dst的编辑距离。 下面具体解释这六种操作的内容即i和j的含义：\ i是src的下标，j是dst的下标。操作开始前，i = j = 0。\ 令x为任意的字符\ copy: dst\[j] = src\[i], i++, j++\ replace: dst\[j] = x, i++, j++\ delete: i++\ insert: dst\[j] = x, j++\ twiddle: dst\[j] = src\[i+1], dst\[j+1] = src\[i], i += 2, j += 2\ kill: 消灭src中剩下的字符。如果执行这个操作，则它必是最的操作。 ## 思考 对于DP问题，首先要想清楚的是初始化过递推。题目中i和j的递增给了很好的提示。\ 定义c\[i,j]为src的子串src\[0,i]变化为dst的子串dst\[0,j]的过程的编辑距离。\ 那么c\[src.length(), dst.length()]即src到dst的编辑距离。\ 这里只是希望操作的个数最少，在操作个数相同的情况下，用什么操作是没有差别的，即每个操作的代价是一样的，即cost(operation) = 1 ### （1）初始化 ``` c[0,0]=0 c[i,0] = i * cost(delete) c[0,j] = j * cost(insert) ``` ### （2）递推 令c\[i, j] = a，根据每个operation的规则，有以下推理 ``` copy: dst[j] = src[i], i++, j++ ==> c[i+1, j+1] = a + cost(copy) replace: dst[j] = x, i++, j++ ==> c[i+1, j+1] = a + cost(replace) delete: i++ ==> c[i+1, j] = a + cost(delete) insert: dst[j] = x, j++ ==> c[i, j+1] = a + cost(insert) twiddle: dst[j] = src[i+1], dst[j+1] = src[i], i += 2, j += 2 ==> c[i+2, j+2] = a + cost(twiddle) kill: 消灭src中剩下的字符。如果执行这个操作，则它必是最的操作。 ``` ### （3）反推 以上推理是基于现在的结果预测后面的结果。\ 然后现在的结果并不能决定后面的结果，但现在的结果一定来自于前面的结果。\ 因此要转换思考方向，将递推进行反推，这一步是DP的难点。\ ![](http://img.my.csdn.net/uploads/201208/30/1346314160_1922.gif) ### （4）最后的操作kill c\[i]\[j] = MIN(c\[m,n], MIN(c\[i,n]+cost(kill)))， 其中0<=i\