yukicoder 225 文字列変更(medium)
問題
方針
このような操作回数のことを Levenshtein distance というのは知っていたので,ググって貼り付けた.
実装
// http://handasse.blogspot.com/2009/04/c_29.html
int const MAX_N = 1010;
int edit_distance_dp(const string& str1, const string& str2){
static int d[MAX_N][MAX_N];
for (int i = 0; i < str1.size() + 1; i++) d[i][0] = i;
for (int i = 0; i < str2.size() + 1; i++) d[0][i] = i;
for (int i = 1; i < str1.size() + 1; i++)
for (int j = 1; j < str2.size() + 1; j++)
d[i][j] = min(min(d[i-1][j], d[i][j-1]) + 1, d[i-1][j-1] + (str1[i-1] == str2[j-1] ? 0 : 1));
return d[str1.size()][str2.size()];
}
int main(){
int n,m;
cin >> n >> m;
string s,t;
cin >> s >> t;
cout << edit_distance_dp(s,t) << endl;
}