首页 > 代码库 > [dp]编辑距离问题

[dp]编辑距离问题

2024-09-21 19:04:16   203人阅读

https://www.51nod.com/tutorial/course.html#!courseId=3

转移方程： 注意如何对齐的。

技术分享

这个算法的特点是，S和T字符串左边始终是对齐的。为了更好地理解这个算法中的递推公式，我们把两个字符串按照特定方式对齐。

以字符串S=ALGORITHM和T=ALTRUISTIC为例：

技术分享

S和T的字符对齐方式为，假设我们已经知道最优的编辑方式：

 

  • 如果删去S中字符，则该字符对齐T中的空格
  • 如果删去T中字符，则该字符对齐S中的空格
  • 如果替换S中字符为T中字符，则这两个字符对齐

 $dp[i][j]$表示字符串s从1到i与字符串t从1到j的最小编辑距离。

 1 #include<bits/stdc++.h> 2 #define INF 0x3f3f3f 3 using namespace std; 4 typedef long long ll; 5 char s[1002],t[1002]; 6 int dp[1002][1002]; 7 int main(){ 8     scanf("%s",s+1); 9     scanf("%s",t+1);10     int n=strlen(s+1);11     int m=strlen(t+1);12     for(int i=0;i<=n;i++){13         for(int j=0;j<=m;j++){14             dp[i][j]=INF;15         }16     }17     for(int i=0;i<=n;i++) dp[i][0]=i;18     for(int j=0;j<=m;j++) dp[0][j]=j;19     20     for(int i=1;i<=n;i++){21         for(int j=1;j<=m;j++){22             dp[i][j]=min(dp[i][j],dp[i-1][j-1]+(s[i]==t[j]?0:1));23             dp[i][j]=min(dp[i][j],dp[i-1][j]+1);24             dp[i][j]=min(dp[i][j],dp[i][j-1]+1);25         }26     }27     28     printf("%d\n",dp[n][m]);29     return 0;30 }

 

[dp]编辑距离问题


联系
我们