线性dp：编辑距离

编辑距离

• 本题与力扣72.编辑距离题意一样，阅读完本文可以尝试leetcode72.
  力扣题目链接

题目叙述

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

输入

NOTV
LOVER

输出

4

题目解释：

动态规划思路

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

状态变量的含义

• 设立一个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]

• 那么我们就很容易的推出我们的递推公式：
  • dp[i][j]=dp[i-1][j-1]（a[i]==b[j]）
  • 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数组

• 举例如下：

代码

• 最终实现代码如下：

#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]);
}