題目

大概（又大概？）就是輸入t組數據，每組數據輸入兩個字符串（又是兩個字符串？） 然后我們可以進行以下操作
1.修改一個字符（如把“a”替換為“b”）
2.刪除一個字符（如把“traveling”變為“travelng”）
然后我們求出讓第一個字符串和第二個字符串相同最少需要幾步操作。

---

輸入

3
abcdefg abcdef
ab ab
mnklj jlknm

輸出

1
0
4

---

解題思路

其實我之前做過一道題叫做編輯距離
網址：這里是網址
跟這題差不多，用f[i][j]表示從a[i]到b[i]的最短編輯距離。
這里列出動態轉移方程：
f[i][j]=min(f[i-1][j-1]+1,f[i-1][j]+1,f[i][j-1]+1)
f[i-1][j-1]+1 表示改變該字符
f[i-1][j]+1 表示刪去A串一個字符
f[i][j-1]+1 表示刪去B串一個字符

---

貼代碼

#include<cstdio> #include<cstring> #include<iostream> using namespace std; int f[1002][1002],n,m,w; char s1[1002],s2[1002]; int main() {scanf("%d",&w);for (int w1=1;w1<=w;w1++){memset(f,0,sizeof(f));//清空scanf("%s%s",s1,s2);m=strlen(s1);n=strlen(s2);for (int i=1;i<=m;i++) f[i][0]=i;//將s1的1-i變為空串就是刪去i個字符，//編輯距離為ifor (int i=1;i<=n;i++) f[0][i]=i;//同上for (int i=1;i<=m;i++)for (int j=1;j<=n;j++)if (s1[i-1]==s2[j-1]) f[i][j]=f[i-1][j-1];//如果兩個字符一樣就不需編輯 else {f[i][j]=min(min(f[i-1][j-1]+1,f[i-1][j]+1),f[i][j-1]+1);//求三種情況的最小值}printf("%d\n",f[m][n]);}return 0; }

總結

以上是生活随笔為你收集整理的OJ4007-计算字符串距离【各种dp之2】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。