题解 P1279 【字串距离】

· · 题解

这一题不算太难

很容易想到状态表示方法：设f ij表示第一个字符串的前i个字符和第二个字符串的前j个字符里的最优值（这个不要问为什么，所有涉及到两个字符串比较的问题比如编辑距离最长公共子序列都是这种状态表示方法）

于是，对于每一个f ij我们考虑第i位和第j位。

这里有三种情况：

  1. 让第i位直接和第j位进行运算，那么转移为前i-1位和前j-1位的问题即f i-1j-1

  2. 让第i位对空格，转移为前i-1位和前j位的问题即f i-1j

  3. 让第j位对空格，转移为前i位和前j-1位的问题即f ij-1

至于那种最优，不知道，取最小的即可

初始化：对于一个字符串中的m位对另一个字符串中的0位的方法是m*k。就是让每一位都对着空格

代码：

#include<bits/stdc++.h>
using namespace std;
int f[2011][2011]={0},l1,l2,k;
string s1,s2;
int main(){
    cin>>s1>>s2>>k;
    l1=s1.size(),l2=s2.size();
    for(int i=1;i<=l1;i++)f[i][0]=i*k;
    for(int i=1;i<=l2;i++)f[0][i]=i*k;
    for(int i=1;i<=l1;i++){
        for(int j=1;j<=l2;j++){
            f[i][j]=min(f[i-1][j]+k,min(f[i-1][j-1]+abs(s1[i-1]-s2[j-1]),f[i][j-1]+k));
        }
    }
    cout<<f[l1][l2]<<endl;
    return 0;
}