编辑距离

编辑距离

这是一个典型的动态规划问题

问题就是给你两个字符串a,b，有三种操作

1. 增加一个字符
2. 删除一个字符
3. 改变一个字符

问通过上述的操作，最少多少步，能把a变为b

直接上代码

#include<bits/stdc++.h>
using namespace std;
int dp[110][110];//dp[i][j]表示a的第一个字符到第i个字符，b的第一个字符到第j个字符
int main()
{
	string a,b;
	cin>>a>>b;
	a=' '+a,b=' '+b;//让字符串从1开始
	int lena=a.size(),lenb=b.size();
	for(int i=0;i<=lenb;i++)	dp[0][i]=i;//如果a字符串为0，那么b字符串有多长，就需要多少步
	for(int i=0;i<=lena;i++)	dp[i][0]=i;//同上
	for(int i=1;i<=lena;i++)
	{
		for(int j=1;j<=lenb;j++)
		{
			dp[i][j]=dp[i-1][j-1]+(a[i]!=b[j]);//如果a的第i个字符与b的第j个字符相等那么就可以转移到dp[i-1][j-1]，不然就需要一步来改变
			dp[i][j]=min(dp[i][j],dp[i-1][j]+1);//删除一个字符
			dp[i][j]=min(dp[i][j],dp[i][j-1]+1);//增加一个字符
		}
	}
	cout<<dp[lena][lenb]<<endl;
	return 0;
}