【CJOJ1644】【洛谷2758】編輯距離

題面

題目描述

設A和B是兩個字元串。我們要用最少的字元操作次數，将字元串A轉換為字元串B。這裡所說的字元操作共有三種：

1、删除一個字元；

2、插入一個字元；

3、将一個字元改為另一個字元；

皆為小寫字母

輸入格式：

第一行為字元串A；第二行為字元串B；字元串A和B的長度均小于2000。

輸出格式：

隻有一個正整數，為最少字元操作次數。

Input

sfdqxbw

gfdgw

Output

4

題解

一道DP裸體

先設一下狀态

設f[i][j]表示串S1前i個字元到串S2前j個字元的編輯距離

看一看每一個f[i][j]可以怎麼得到：

如果目前有S1[i]=S2[j]那麼f[i][j]=f[i-1][j-1]，直接由前面的狀态就可以得到

否則：

1. 可以由i-1和j-1的比對情況加上一次修改操作

2. 可以由i-1和j 的比對情況加上一次删除操作

3. 可以由i 和j-1的比對情況加上一次添加操作

是以狀态轉移方程就可以得出來了

後面就不用寫了，直接看代碼吧

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
using namespace std;
string s1,s2;//初始字元串 
int l1,l2;
int f[][];
int main()
{
      cin>>s1>>s2;
      l1=s1.length();
      l2=s2.length();
      memset(f,,sizeof(f));
      //f[i][j]表示把 s1前i位變為 s2的前j位的 最短編輯距離 
      for(int i=;i<=l2;++i)
         f[][i]=i;
      for(int i=;i<=l1;++i)
         f[i][]=i;
      for(int i=;i<=l1;++i)
      {
             for(int j=;j<=l2;++j)
             {
                     if(s1[i-]==s2[j-])
                        f[i][j]=min(f[i][j],f[i-][j-]);//如果兩位相同 
                     else 
                     f[i][j]=min(f[i][j],f[i-][j-]+);//上一位的基礎上加"替換"
                     f[i][j]=min(f[i][j],f[i][j-]+);//上一個的基礎上加"添加"
                     f[i][j]=min(f[i][j],f[i-][j]+);//上一位的基礎上加"删除" 

             }
      }
      cout<<f[l1][l2]<<endl;
      return ;
}