前言

内容写作不易，求赞！

题面大意

给定两个字符串 A 和 B，你可以：

1、删除一个字符；

2、插入一个字符；

3、将一个字符改为另一个字符。

问你将字符串 A 变换为字符串 B 所用的最少字符操作次数。

算法分析

暴力

是个人都会写。

动态规划

我们发现，这个操作只更改一个字符，别的字符不受影响，考虑 dp。

由于对于字符串的操作只有 $4$ 种情况（分别是：删除，添加、更改、不变），我们可以从这里下手设计转移方程。

我们可以设 $f_{i,j}$ 表示将 A 的前 $i$ 个字符变为 B 的前 $j$ 个字符的编辑距离。

因为它们最后相等了，所以它们的末尾字符肯定也相等。

• 删除操作：我们设删除 A 的末尾字符，则为 $f_{i-1,j}$，由于此操作需要一步，所以还要 $+1$。

• 插入操作：假设在 A 末尾添加字符，我们想：插入到最后，就是插入 B 的末尾字符，这样就可以转移到 $f_{i,j-1}$ ，当然还要 $+1$。

• 替换操作：还是假设更改最后一个字符，改之前它们不相等，所以考虑前面的串的次数即可，即 $f_{i-1,j-1}+1$

• 不变的话显然是 $f_{i-1,j-1}$（最后本来都相等了，当然就是前面的次数了）

求最小值即可。

整理出转移方程：

$$f_{ij}=\min\{f_{i-1,j},f_{i,j-1},f_{i-1,j-1},f_{i-1,j-1}-1\}+1 $$

时间复杂度 $\mathcal{O}(nm)$（设 A,B 的长度分别为 $n,m$）

代码

代码就不放了，大家自己看懂上面的转移方程那不就会写了。

【例9.20】编辑距离

好坐牢的shi东西

题意

设A和B是两个字符串。我们要用最少的字符操作次数，将字符串A转换为字符串B。这里所说的字符操作共有三种：

1、删除一个字符；

2、插入一个字符；

3、将一个字符改为另一个字符。

对任意的两个字符串A和B，计算出将字符串A变换为字符串B所用的最少字符操作次数。

思路

由于是万恶的DP，所以我们直接开一个二维数组int f[N][N]来计算

之后便是赋值操作，先给A删一点东西，删到空

for(int i=0;i<a.length();++i)
  f[i][0]=i;//计算删除操作的“贡献”

再给B删到空

for(int i=0;i<b.length();++i)
  f[0][i]=i;//计算删除操作的“贡献”

之后是我们的 DP 算法！

由于此前已经删过了，所以我们只考虑插入和更改操作。

两层循环，一直扫描两个串

for(int i=0;i<a.length();++i)
  for(int j=0;j<b.length();++j)

如果a[i]==b[j]，不用修改，直接照抄上个状态（防止越界要加 1）

if(a[i]==b[j])
  f[i+1][j+1]=f[i][j];

否则，考虑三种操作

• 插入操作，假设 a 插入 b 末尾的字符，则该状态是 f[i+1][j]

• 插入操作，假设 b 插入 a 末尾的字符，则该状态是 f[i][j+1]

• 修改操作，假设修改 a 末尾的字符则该状态是 f[i][j]

上述三种状态的次数取最优（即 min），别忘了加上贡献（+1）

此时可以得出方程$$ f[i][j]=min{f[i][j-1],f[i-1][j],f[i-1][j-1]}+1; $$

AC damn马

#include<iostream>
#include<string>
#include<algorithm>
#include<cmath>
#define N 2002

using namespace std;

string a,b;
int f[N][N]={},la,lb;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	cin>>a>>b;
	
	la=a.length();
	lb=b.length();
	
	for(int i=0;i<la;++i)
		f[i][0]=i;	//计算删除操作的“贡献”
	for(int i=0;i<lb;++i)
		f[0][i]=i;	//计算删除操作的“贡献”
	
	for(int i=1;i<=la;++i)
		for(int j=1;j<=lb;++j)
		{
			if(a[i-1]==b[j-1])
				f[i][j]=f[i-1][j-1];	//字符相同则照抄上个状态 
			else
				f[i][j]=min(f[i][j-1],min(f[i-1][j],f[i-1][j-1]))+1;	//否则，计算此时最优解 
		}
		
	cout<<f[la][lb];
	
	return 0;
}

代码

#include <bits/stdc++.h>
using namespace std;
string a,b;
int f[1005][1005];
int main(int argc, char **argv){
	cin >> a >> b;
	int l1 = a.size(),l2 = b.size();
	// memset(f,0,sizeof(f));
	for (int i = 1;i <= l1;i++)	f[i][0] = i;
	for (int j = 1;j <= l2;j++)	f[0][j] = j;

	for (int i = 1;i <= l1;i++){
		for (int j = 1;j <= l2;j++){
			int si = i - 1,sj = j - 1;
			if (a[si] == b[sj])	f[i][j] = f[i - 1][j - 1];
			else	f[i][j] = min({f[i - 1][j - 1],f[i - 1][j],f[i][j - 1]}) + 1;
		}
	}
	printf("%d",f[l1][l2]);
	return 0;
}

#include <bits/stdc++.h>
using namespace std;
string a,b;
int ans[1005][1005];
int main(){
	cin>>a>>b;
	for(int i=1;i<=a.size();i++)ans[i][0]=i;
	for(int j=1;j<=b.size();j++)ans[0][j]=j;
	for(int i=1;i<=a.size();i++)for(int j=1;j<=b.size();j++)(a[i-1]==b[j-1])?(ans[i][j]=ans[i-1][j-1]):(ans[i][j]=min({ans[i-1][j-1],ans[i-1][j],ans[i][j-1]})+1);
	cout<<ans[a.size()][b.size()];
	return 0;
}

#include<bits/stdc++.h>
using namespace std;
int f[4016][4016];
string s1,s2;
int m,n;
int main(){
	 cin>>s1>>s2;
	 m=s1.length();
	 n=s2.length();
	 for(int i=1;i<=m;i++){
	 	f[i][0]=i;
	 }
	 for(int i=1;i<=n;i++){
	 	f[0][i]=i;
	 }
	 for(int i=1;i<=m;i++){
	 	for(int j=1;j<=n;j++){
	 		if(s1[i-1]==s2[j-1])f[i][j]=f[i-1][j-1];
	 		else f[i][j]=min(min(f[i-1][j],f[i][j-1]),f[i-1][j-1])+1;
	 	}
	 }
	 cout<<f[m][n]<<endl;
}

from 军舰

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
#define INF 0x3f3f3f3f
#define M 3000
int f[M][M];
int len_a, len_b;
char a[M], b[M];
int main() {
	scanf("%s", a);
	getchar();
	scanf("%s", b);
	len_a = strlen(a);
	len_b = strlen(b);
	for(int i = 1; i <= len_a; i++) f[i][0] = i;
	for(int i = 1; i <= len_b; i++) f[0][i] = i; 
	for(int i = 1; i <= len_a; i++) {
		for(int j = 1; j <= len_b; j++) {
			if(a[i-1] == b[j-1]) {
				f[i][j] = f[i-1][j-1];
			}
			else f[i][j] = min(min(f[i-1][j], f[i][j-1]), f[i-1][j-1]) + 1;
		}
	}
	printf("%d\n", f[len_a][len_b]);
	return 0;
}

#include<bits/stdc++.h>
using namespace std;
int main(){
	int dp[190012];
	string s,t;
	cin>>s>>t;
	int n= s.length(), m=t.length();
	for(int j=1;j<=m;j++){
		dp[j]=j;
	}
	for(int i=1;i<=n;i++){
		int leftup=dp[0];
		dp[0]=i;
		for(int j=1;j<=m;j++){
			int temp=dp[j];
			if(s[i-1]==t[j-1]){
				dp[j]=leftup;
			}else{
				dp[j]=min(min(dp[j-1],dp[j]),leftup)+1;
			}
			leftup=temp;
		}
	}
	cout<<dp[m];
}