线性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]
- 1.若
- 那么我们就很容易的推出我们的递推公式:
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]);
}