# 【題解】ZeroJudge e828: 3.猴子打字遊戲 (Typing)

【範例】Edit Distance
【題目敘述】https://zerojudge.tw/ShowProblem?problemid=e828
【解題想法】DP，Edit Distance，滾動陣列【參考資料

```#include <iostream>
#include <cstring>
using namespace std;
string s1, s2;

int editDistance(){
int len1 = (int) s1.length();
int len2 = (int) s2.length();

int dp[2][len1 + 1];
memset(dp, 0, sizeof dp);

//s2 為空字串
for (int i = 0; i <= len1; i++)
dp[0][i] = i * 2; //add

for (int i = 1; i <= len2; i++) {
for (int j = 0; j <= len1; j++) {
if (j == 0) //s1 為空字串
dp[i % 2][j] = i * 2; //delete
else if (s1[j - 1] == s2[i - 1]) {
dp[i % 2][j] = dp[(i - 1) % 2][j - 1];
} else {
dp[i % 2][j] = min(dp[(i - 1) % 2][j] + 2,
min(dp[i % 2][j - 1] + 2,
dp[(i - 1) % 2][j - 1] + 3));
}
}
}
return dp[len2 % 2][len1];
}

int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> s1;
int mn = 1e9, idx = 0;
for (int i=1; i<=3; i++){
cin >> s2;
int dis = editDistance();
if (dis <= mn){
mn = dis;
idx = i;
}
}
cout << idx << " " << mn << "\n";
return 0;
}

```

Python code (credit: Amy Chou)
⚠️注意：NA (score:60%)：測資#12 ～ #19 TLE.

```import sys

def editDistance():
len1 = len(s1)
len2 = len(s2)
dp = [[0 for j in range(len1+1)] for i in range(2)]
for i in range(len1+1):
dp[0][i] = i * 2 # add

for i in range(1, len2+1):
for j in range(len1+1):
if j == 0:
dp[i%2][j] = i * 2
elif s1[j-1] == s2[i-1]:
dp[i%2][j] = dp[(i-1)%2][j-1]
else:
dp[i%2][j] = min([
dp[(i-1)%2][j] + 2,
dp[i%2][j-1] + 2,
dp[(i-1)%2][j-1] + 3,
])
return dp[len2 % 2][len1]