题解：P2758 编辑距离

第一步：确定子问题

有4种操作（删除，添加，修改，不变）。所以4个子问题就是操作后的A变为B需要多少步。

第二步：确定状态

设 $dp[i][j]$ 为将A的前i位变为B的前j位的最小代价。

第三步：确定转移方程

1. 删除: $dp[i][j]=dp[i-1][j]+1$
2. 添加: $dp[i][j]=dp[i][j-1]+1$
3. 修改: $dp[i][j]=dp[i-1][j-1]+1$
4. 不变: $dp[i][j]=dp[i-1][j-1]$

第四步：寻找边界条件

$dp[0][i]=i(0\le i\le |B|)$

$dp[i][0]=i(0\le i\le |A|)$

代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;
string a,b;
ll dp[2005][2005];
signed main(){
	ios::sync_with_stdio(false);
	cin>>a>>b;a='.'+a;b='.'+b;
	ll n=a.size()-1,m=b.size()-1;
	memset(dp,0x3f,sizeof(dp));
	for(ll i=0;i<=m;i++)dp[0][i]=i;
	for(ll i=0;i<=n;i++)dp[i][0]=i;
	for(ll i=1;i<=n;i++)
		for(ll j=1;j<=m;j++){
			if(a[i]==b[j]){
				dp[i][j]=dp[i-1][j-1];
				continue;
			}
			dp[i][j]=min(dp[i][j],dp[i-1][j]+1);
			dp[i][j]=min(dp[i][j],dp[i][j-1]+1);
			dp[i][j]=min(dp[i][j],dp[i-1][j-1]+1);
		}
	cout<<dp[n][m];
	return 0;
}