アルゴリズム勉強会でDPの問題を解くようになり、ふと思い出したので復習してみた。レーベンシュタイン距離とは、2つの文字列X,Yの類似度を定量的に表現するための指標である。 dp[i][j] を文字列Xのi文字目と文字列Yのj文字目までのレーベンシュタイン距離…