[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]$那顯然不需要作修改，而若不同，則看看用插入、刪除或取代哪個比較好。

#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;
}