P2758 编辑距离

[MIku]（https://www.luogu.com.cn/problem/P2758）

定义\(dp_{i,j}\)为把\(A_{1-i}\)变为\(B_{1-j}\)得最小花费

可以由\(dp_{i-1,j}\)转移，把\(A_{i}\)删了

\(dp_{i,j-1}\) 最后加个\(B_{j}\)

\(dp_{i-1,j-1}\) 把\(A_i\)改成\(B_j\)并且显然，若他们相等，就不用操作

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
string a,b;
int dp[2001][2001];
int la,lb;
int c;
int main(){
	cin>>a>>b;
	la=a.length();
	lb=b.length();
	c=max(la,lb);
	for(int i=1;i<=c;++i){
		dp[i][0]=dp[0][i]=i;
	}
	for(int i=1;i<=la;++i){
		for(int j=1;j<=lb;++j){
			if(a[i-1]==b[j-1]){
				dp[i][j]=dp[i-1][j-1];
			}else{
				dp[i][j]=min(min(dp[i-1][j],dp[i][j-1]),dp[i-1][j-1])+1;
			}
		}
	}
	cout<<dp[la][lb];
	return 0;
} 

P2758 编辑距离

原文：https://www.cnblogs.com/For-Miku/p/13493323.html