ZJU/ZOJ 1459 String Distance and Transform Process 解题报告

题目大意是给定两个字符串，要求通过插入、删除、替换这三种操作来将第一个字符串转化为第二个字符串，问最少需要的操作次数以及具体的操作方案。

模型很明显是最长公共子串，同样是分两种两种情况考虑，s1[i]=s2[j]时，f[i,j]=min(f[i-1,j-1],f[i-1,j]+1,f[i,j-1]+1)，分别对应第一个字符串的第i个字符与第二个字符串的第j个字符匹配、删除第一个字符串的第i个字符、在第一个字符串的第i+1位插入第二个字符串的第j位字符；s1[i]<>s2[j]时，f[i,j]=min(f[i-1,j-1]+1,f[i-1,j]+1,f[i,j-1]+1)，分别对应第一个字符串的第i个字符替换为第二个字符串的第j个字符、删除第一个字符串的第i个字符、在第一个字符串的第i+1位插入第二个字符串的第j位字符。f[i,j]则表示第一个字符串的前i个字符转化为第二个字符串前j个字符所需的最少操作次数。在DP过程中记录下每次状态转移对应的具体的操作，则可以通过倒推输出所有操作步骤。

3069395    2008-09-14 13:41:20    Accepted    1459    FPC    00:00.06    420K    IwfWcf