【範例】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]
lines = sys.stdin.readlines()
s1 = lines[0].strip()
mn = 1000000000
idx = 0
for i in range(1, 4):
s2 = lines[i].strip()
dis = editDistance();
if (dis <= mn):
mn = dis
idx = i
print(idx, mn)