【9916】编辑距离

Time Limit: 1 second
Memory Limit: 128 MB

【问题描述】

设A和B是两个字符串。我们要用最少的字符操作次数，将字符串A转换为字符串B。这里所说的字符操作共有三种：
1、删除一个字符；
2、插入一个字符；
3、将一个字符改为另一个字符。
【编程任务】
对任的两个字符串A和B，计算出将字符串A变换为字符串B所用的最少字符操作次数。
【输入格式】

第一行为字符串A；第二行为字符串B；字符串A和B的长度均小于200。
【输出格式】

只有一个正整数，为最少字符操作次数。

Sample Input

sfdqxbw
gfdgw

Sample Output

【题目链接】:http://noi.qz5z.com/viewtask.asp?id=9916

【题解】

设f[i][j]表示第一个串s1[1..i]变成s2[1..j]要进行多少次操作;
则两层循环枚举两个串的每个字符；
①s1[i]==s2[j];则f[i][j] = f[i-1][j-1];
表示s1[1..i]变成s2[1..j]的问题可以转化为s1[1..i-1]变成s2[1..j-1]的问题(s1[1..i-1]变成s2[1..j-1]之后因为s1[i]==s1[j]所以不用进行任何操作了);
②s1[i]!=s2[j]
f[i][j] = min(f[i-1][j]+1,min(f[i][j-1]+1,f[i-1][j-1]+1));
1’:f[i-1][j]+1表示删除操作;
即s1[1..i-1]变成s2[1..j];然后在s1[i-1]后面把s1[i]删掉这样就在s1[1..i-1]变成s2[1..j]基础上再增加一次删除操作;
2’:f[i][j-1]+1表示添加操作;
即s1[1..i]变成s2[1..j-1];然后在s1[i]的后面再添加一个s[j];这样s1[1..i]==s2[1..i];
3’:f[i-1][j-1]+1;表示修改操作；
s1[1..i-1]变成s2[1..j-1];
然后再s1[i]改成s2[j];
边界:
f[0][i]=i;//添加i个字符(每个字符都和s2相同);
f[i][0]=i;//删掉i个字符(s2为空);

【完整代码】

#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <set>
#include <map>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
#include <vector>
#include <stack>
#include <string>
using namespace std;
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define LL long long
#define rep1(i,a,b) for (int i = a;i <= b;i++)
#define rep2(i,a,b) for (int i = a;i >= b;i--)
#define mp make_pair
#define pb push_back
#define fi first
#define se second

typedef pair<int,int> pii;
typedef pair<LL,LL> pll;

void rel(LL &r)
{
    r = 0;
    char t = getchar();
    while (!isdigit(t) && t!='-') t = getchar();
    LL sign = 1;
    if (t == '-')sign = -1;
    while (!isdigit(t)) t = getchar();
    while (isdigit(t)) r = r * 10 + t - '0', t = getchar();
    r = r*sign;
}

void rei(int &r)
{
    r = 0;
    char t = getchar();
    while (!isdigit(t)&&t!='-') t = getchar();
    int sign = 1;
    if (t == '-')sign = -1;
    while (!isdigit(t)) t = getchar();
    while (isdigit(t)) r = r * 10 + t - '0', t = getchar();
    r = r*sign;
}

const int MAXN = 2000;
const int INF = 0x3f3f3f3f;
const int dx[9] = {0,1,-1,0,0,-1,-1,1,1};
const int dy[9] = {0,0,0,-1,1,-1,1,-1,1};
const double pi = acos(-1.0);

int f[MAXN][MAXN];
char s1[MAXN],s2[MAXN];
string ss;
int main()
{
    memset(f,INF,sizeof(INF));
    scanf("%s",s1+1);
    scanf("%s",s2+1);
    int len1 = strlen(s1+1),len2 = strlen(s2+1);
    f[0][0] = 0;
    rep1(i,1,len1)
        f[i][0] = i;
    rep1(i,1,len2)
        f[0][i] = i;
    rep1(i,1,len1)
        rep1(j,1,len2)
            if (s1[i]==s2[j])
                f[i][j] = f[i-1][j-1];
            else
                f[i][j] = min(f[i-1][j]+1,min(f[i][j-1]+1,f[i-1][j-1]+1));
    cout << f[len1][len2];
    return 0;
}