P2758 编辑距离

点击查看代码

#include<bits/stdc++.h>
using namespace std;const int N=2010;string a,b;
int dp[N][N];int main()
{ios::sync_with_stdio(0),cin.tie(0);cin>>a>>b;int n=a.length();int m=b.length();a=" "+a;b=" "+b;for(int i=1;i<=n;i++) dp[i][0]=i;for(int j=1;j<=m;j++) dp[0][j]=j;for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){if(a[i]==b[j]){dp[i][j]=dp[i-1][j-1];}else{dp[i][j]=min({dp[i-1][j],dp[i][j-1],dp[i-1][j-1]})+1;}}}cout<<dp[n][m]<<"\n";return 0;}