POJ 3356 AGTC

問題文

DP強化週間。

文字列が2つ与えられる。それらの文字列の適切な位置に文字を挟む、消去する、文字を変えるなどして、2つの文字列を同じにしたい。そのために必要な処理の回数を求める問題。

要は編集距離。
dp[i+1][j+1]:=(文字列1のi番目と文字列2のj番目までの編集距離)でDP。
以下ソース。

int dp[1001][1001];
int main(int argc, char **argv){
  int M, N;
  string s, t;
  while(cin >> M >> s >> N >> t){
    memset(dp, 0, sizeof(dp));
    for(int i = 0; i <= M; i++) dp[i][0] = i;
    for(int j = 0; j <= N; j++) dp[0][j] = j;

    for(int i = 0; i < M; i++){
      for(int j = 0; j < N; j++){
	int cost = (s[i] == t[j]) ? 0 : 1;
	dp[i + 1][j + 1] = min(dp[i + 1][j] + 1,
			                       min(dp[i][j + 1] + 1,
				                       dp[i][j] + cost));
      }
    }
    cout << dp[M][N] << endl;
  }
  return 0;
}

何度出してもWAが取れなかった。
複数テストケースだった。書いとかなきゃいかんでしょ。