yukicoder 225 文字列変更(medium)

2015/06/20 (Sat) yukicoder 文字列 DP

問題

問題文

方針

このような操作回数のことを 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;
}