動的計画法(DP)は複雑な問題をより小さく単純な部分問題に分割し解決する手法です。その中には文字列メトリクスに対して効果的なパターンもいくつかあり、このシリーズはそれらに関する私のまとめノートです。何か追加すべきものがあると思われる場合は、お気軽にお問い合わせください。

記事リスト

読む前提条件

出来るだけ噛み砕いて説明するよう努力していますが、基本的な動的計画法自体の説明になっているかどうかは自信がありませんので、DP 自体への入門はこちらの記事を参照していただけたらと思います。

理解のコツ：DP テーブルの初期化と更新

DP の解法や実装方法はいくつかあるのですが、このシリーズでは所謂ボトムアップというアプローチを使っています。トップダウンでは再帰が使われるのに対し、ボトムアップはテーブル（タブとも呼ばれる）が使われ可視化しやすいので自分もボトムアップで理解することの方が多いです。

レーベンシュタイン距離の例：

dax86-xv6

このシリーズは文字列に対する動的計画法をまとめていますが、問題によりその応用は様々です。それらを頭の中で整理するコツは DP テーブルが目的に応じてどのように初期化されるか、そしてどの様に更新されるかを問題毎に理解することだと思います。

鍵となるテーブル更新の実装部分：

1
2
3
4
5
6
7

if s[i-1] == target[j-1]:  # if characters are identical, cost is 0
    substitute_cost = 0
else:
    substitute_cost = 1
dp[i][j] = min(dp[i-1][j] + 1,  # delete
                dp[i][j-1] + 1,  # insert
                dp[i-1][j-1] + substitute_cost)  # substitute