线性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("%dn",f[la][lb]); }