题目内容

P2758

给定三种字符串操作,分别是插入,修改和删除(都针对一个字符),求字符串 a 变化为 b 的最小操作次数

解题思路

经典的 dp 问题,考虑如何设计状态使得状态不具后效性并且满足最优子结构。不妨假设两个字符串的下标都从 1 开始,并定义 f_{i,j} 为字符串 1 的前 i 位转为字符串 2 的前 j 位所需的最少操作次数。不难发现这样定义的状态满足上述性质,所以开始设计转移。

上面提到有三种基本的操作,因此考虑怎样操作能使得次数最小化。如果是在串 1 的后面添加字符,则状态由 f_{i,j-1}+1 转移而来,如果是删除字符,则由 f_{i-1,j}+1 转移而来,如果是改变字符,那就从 f_{i-1,j-1}+1 转移而来。特别的,如果当前涉及到的这两个字符串的对应位是相同的,改变字符的操作就不需要加一了。而为了使当前的 f_{i,j} 最优,我们需要将前面所有能到达 f_{i,j} 的决策取最小值。转移方程如下:

定义变量 k,当 a_i=b_i 时,k=0,反之 k=1,方程如下:

f_{i,j}=\min(f_{i-1,j}+1,f_{i,j-1}+1,f_{i-1,j-1}+k)

写出了方程,要注意的是边界条件。所有的 f_{i,0} 都为 i,所有的 f_{0,j} 都为 j。我们要输出的是 f_{l_1,l_2},搞清楚以上几点,就可以写代码了

#include <cstdio>
#include <cstring>

char s1[2010],s2[2010];
int f[2010][2010];

inline int min(int a,int b)
{
    return a<b?a:b;
}

int main()
{
    scanf("%s",s1+1);
    scanf("%s",s2+1);
    int l1=strlen(s1+1),l2=strlen(s2+1);//都是为了字符串下标做的处理
    memset(f,0x3f3f3f3f,sizeof(f));
    for(int i=0;i<=l1;i++)
        f[i][0]=i;
    for(int i=0;i<=l2;i++)
        f[0][i]=i;
    for(int i=1;i<=l1;i++)
        for(int j=1;j<=l2;j++)
        {
            if(s1[i]!=s2[j])//如果对应位不相等
                f[i][j]=min(f[i-1][j-1]+1,min(f[i-1][j]+1,f[i][j-1]+1));
            else
                f[i][j]=min(f[i-1][j-1],min(f[i-1][j]+1,f[i][j-1]+1));
        }
    printf("%d\n",f[l1][l2]);
    return 0;
}
最后修改日期:2020年3月14日

作者

留言

撰写回覆或留言

发布留言必须填写的电子邮件地址不会公开。