編集距離 O(N^2) DP

Quiz

https://yukicoder.me/problems/no/225

AC

https://yukicoder.me/submissions/408789

解説

  • 編集距離そのものの問題
int dp[1050][1050];

i : sのi文字目
j : tのj文字目
までを一致させるための最小コスト
  • としてDPで解く。O(N2)

Code

// 編集距離
const int MAX_LEN = 1050;
ll edit_distance(string& s, string& t){
  ll N = s.size();
  ll M = t.size();
  VV dp(MAX_LEN, VI(MAX_LEN, inf));
  rep(i, MAX_LEN){
    dp[0][i] = i;
    dp[i][0] = i;
  }

  rep(i, N){
    rep(j, M){
      if(s[i]==t[j]){
        ll a = dp[i][j];
        ll b = dp[i][j+1] + 1;
        ll c = dp[i+1][j] + 1;
        dp[i+1][j+1] = min({a, b, c});
      }else{
        ll a = dp[i][j] + 1;
        ll b = dp[i][j+1] + 1;
        ll c = dp[i+1][j] + 1;
        dp[i+1][j+1] = min({a, b, c});
      }
    }
  }
  return dp[N][M];
}