[TIOJ] 1385. 芳佳的打工
題目連結:http://tioj.infor.org/problems/1385
本題有空白!!!裸的Edit Distance題,不過要注意要吃一整行,不要只讀一段進來,不然會WA。稍微解釋一下DP式,$dp[i][j]$代表用a的前i個字元轉換成b的前j個字元所需的最少次數,那轉移就會是$dp[i][j] = \begin{cases} dp[i-1][j-1],& \text{if } a[i-1] = b[j-1]\\ \min(dp[i][j-1], dp[i-1][j], dp[i-1][j-1])+1, & \text{otherwise} \end{cases}$,因為如果$a[i]==b[j]$那顯然不需要作修改,而若不同,則看看用插入、刪除或取代哪個比較好。
本題有空白!!!裸的Edit Distance題,不過要注意要吃一整行,不要只讀一段進來,不然會WA。稍微解釋一下DP式,$dp[i][j]$代表用a的前i個字元轉換成b的前j個字元所需的最少次數,那轉移就會是$dp[i][j] = \begin{cases} dp[i-1][j-1],& \text{if } a[i-1] = b[j-1]\\ \min(dp[i][j-1], dp[i-1][j], dp[i-1][j-1])+1, & \text{otherwise} \end{cases}$,因為如果$a[i]==b[j]$那顯然不需要作修改,而若不同,則看看用插入、刪除或取代哪個比較好。
#include <bits/stdc++.h>
using namespace std;
const int N = 1000 + 5;
int dp[N][N];
int main(){
string a, b;
getline(cin, a);
getline(cin, b);
int lenA=a.size(), lenB=b.size();
for(int i=0;i<=lenA;i++) dp[i][0] = i;
for(int i=0;i<=lenB;i++) dp[0][i] = i;
for(int i=1;i<=lenA;i++){
for(int j=1;j<=lenB;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], dp[i][j-1], dp[i-1][j-1]})+1;
}
}
cout<<dp[lenA][lenB]<<'\n';
return 0;
}
留言
張貼留言