DP例题详解(二)最短编辑距离和编辑距离

 902. 最短编辑距离 - AcWing题库

 

#include<bits/stdc++.h>

using namespace std;

const int N=1010;
 
int n,m;
char a[N],b[N];
int f[N][N];

int main()
{
	cin>>n>>a+1;
	cin>>m>>b+1;
	for(int i=0;i<=m;i++)f[0][i]=i;
	for(int i=0;i<=n;i++)f[i][0]=i;//先初始化
	
	for(int i=1;i<=n;i++)
	for(int j=1;j<=m;j++)
	{
		f[i][j]=min(f[i-1][j]+1,f[i][j-1]+1);
		if(a[i]==b[j])f[i][j]=min(f[i][j],f[i-1][j-1]);
		else f[i][j]=min(f[i][j],f[i-1][j-1]+1);//做删的操作 
	 } 
	 cout<<f[n][m];
	 
	 return 0;
}

 二,编辑距离 899. 编辑距离 - AcWing题库

#include<bits/stdc++.h>

using namespace std;

const int N=15,M=1010;

int n,m;
int f[N][N];
char str[M][N];

int check(char a[],char b[])
{
	int la=strlen(a+1),lb=strlen(b+1);
	
	for(int i=1;i<=la;i++)f[0][i]=i;
	for(int i=1;i<=lb;i++)f[i][0]=i;//先初始化
	
	for(int i=1;i<=la;i++)
	for(int j=1;j<=lb;j++)
	{
		f[i][j]=min(f[i-1][j]+1,f[i][j-1]+1);
		if(a[i]==b[j])f[i][j]=min(f[i][j],f[i-1][j-1]);
		else f[i][j]=min(f[i][j],f[i-1][j-1]+1);//做删的操作 
	 } 
	 return f[la][lb];
}

int main()
{
	cin>>n>>m;
	for(int i=0;i<n;i++)
	{
		cin>>str[i]+1;
	}
	while(m--)
	{
		char s[N];
		int limit;
		cin>>s+1>>limit;
		
		int res=0;
		for(int i=0;i<n;i++)
		{
			if(check(str[i],s)<=limit)
			res++;
		}
		cout<<res<<endl;
	} 
	return 0;
}