解题步骤:
参考代码:
int main()
{
string s1;
string s2;
while (cin >> s1 >> s2)
{
int m=s1.size();
int n=s2.size();
//增加空白字符,修正下标的映射关系
s1=' '+s1;
s2=' '+s2;
//多卡一行,多开一列
vector<vector<int>> dp(m+1,vector<int>(n+1));
//初始化
for(int i=0;i<=m;i++)
{
dp[i][0]=i;
}
for(int j=0;j<=n;j++)
{
dp[0][j]=j;
}
for(int i=1;i<=m;i++)
{
for(int j=1;j<=n;j++)
{
//状态转移方程
if(s1[i]==s2[j])
{
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[m][n]<<endl;
}
return 0;
}
你学会了吗???