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