yukicoder No.225 文字列変更(medium)

解き方わかっていたのに、配列初期化をちゃんとできていなかったり、変換前と変換後を逆にしていたりなどでバグらせてしまい、時間内に提出できませんでした…（終了3分後に解けました…）

• 問題: http://yukicoder.me/problems/610
• 提出: http://yukicoder.me/submissions/32188
• 解答時間40分くらい、WA 0回

解法としてはDPする感じです。蟻本で最長共通部分列問題というのを調べてみればいいみたいです。なんとなくソースコードみて察してください。

ソースコード

int main(int argc, const char * argv[]){
    int n, m;
    cin >> n >> m;
    string s, t;
    cin >> s >> t;
    int editCount[1001][1001];
    int inf = 1<<28;
    REP(i, n+1) {
        REP(j, m+1) {
            editCount[i][j] = inf;
        }
    }
    editCount[0][0] = 0;
    
    REP(i, n+1) {
        REP(j, m+1) {
            // 文字を追加する
            if(i <= n) {
                editCount[i][j+1] = min(editCount[i][j+1], editCount[i][j] + 1);
            }
            
            // 文字を削除する
            if(j <= m) {
                editCount[i+1][j] = min(editCount[i+1][j], editCount[i][j] + 1);
            }
            
            // 文字を変更する
            if(s[i] == t[j]) {
                editCount[i+1][j+1] = min(editCount[i+1][j+1], editCount[i][j]);
            } else {
                editCount[i+1][j+1] = min(editCount[i+1][j+1], editCount[i][j] + 1);
                
            }
        }
    }
    
    cout << editCount[n][m];
}