编辑距离

<li>本题与力扣72.编辑距离题意一样，阅读完本文可以尝试leetcode72.

力扣题目链接

li>

题目叙述

输入两个字符串a，b。输出从字符串a修改到字符串b时的编辑距离

输入

NOTV

LOVER

输出

4

题目解释：

动态规划思路

<li>这个问题显然是一个最优解问题，我们可以考虑动态规划的思路，那么我们使用动态规划的思路，要想得到最优解问题，那么我们必须要先考虑子问题。
• 子问题：我们先考虑<code>a[1,2...i]到b[1,2....j]的编辑距离li>

状态变量的含义

• 设立一个dp数组，作为我们的状态变量
  • dp[i][j]表示以从a[1...i]到b[1....j]的编辑距离

递推公式

• 设立完状态变量，那么我们就进入了递推公式的推导
  • 1.若a[i]=b[j]，那么dp[i][j]==dp[i-1][j-1]
  • 2.a[i]!=b[j]

<li>那么我们就很容易的推出我们的递推公式：
• <code>dp[i][j]=dp[i-1][j-1]（a[i]==b[j]）li>
• dp[i][j]=min(dp[i-1][j-1],dp[i][j-1],dp[i-1][j])+1）（a[i]!=b[j]）

遍历顺序

• 显然是从上到下，从左到右。

初始化dp数组

• 边界条件：

  • f[i][0]=i
  • f[0][j]=j

• 对应的初始化代码如下：

m=strlen(a);

n=strlen(b);

for(int i=1;i<=m;j++) dp[i][0]=i;

for(int j=1;j<=n;j++) dp[0][j]=j;

for(int i=1;i<=m;i++){

for(int j=1;j<=n;j++){

if(a[i-1]==b[j-1]) dp[i][j]=dp[i-1][j-1];

else dp[i][j]=min(dp[i-1][j-1],min(dp[i][j-1],dp[i-1][j])+1;

}

}

cout<<f[m][n];

举例打印dp数组

• 举例如下：

代码

<li>最终实现代码如下：

<code>#include<iostream>

#include<cstring>

#include<algorithm>

using namespace std;

char a[2005],b[2005];

int f[2005][2005];

int main(){

scanf("%s %s",a,b);

int la=strlen(a), lb=strlen(b);

for(int i=1;i<=la;i++) f[i][0]=i;

for(int i=1;i<=lb;i++) f[0][i]=i

for(int i=1;i<=la;i++)

for(int j=1;j<=lb;j++)

if(a[i-1]==b[j-1])f[i][j]=f[i-1][j-1];

else f[i][j]=min(min(f[i-1][j],f[i][j-1]),f[i-1][j-1])+1;

printf("%d\n",f[la][lb]);

}