Levenshtein distance レーベンシュタイン距離

アルゴリズム勉強会でDPの問題を解くようになり、ふと思い出したので復習してみた。

レーベンシュタイン距離とは、2つの文字列X,Yの類似度を定量的に表現するための指標である。
dp[i][j] を文字列Xのi文字目と文字列Yのj文字目までのレーベンシュタイン距離とすると、dp[i][j]は帰納的にdp[i-1][j]、dp[i][j-1]、dp[i-1][j-1]から求まる。dp[i-1][j]、dp[i][j-1]はそれぞれ1だけ距離を足してあげればよく、dp[i-1][j-1]に関しては、i,j文字目が等しい場合は距離は変更ないので0,等しくない場合は1距離を足せばdp[i][j]と一致するはずである。これをやっているのが二重ループの箇所である。

DPを最初に考えたRichard Bellmanはまじ天才である。