動的計画法

ゼミの発表の為に動的計画法について少し読んでみた。
以前レーベンシュタイン距離（2つの文字列がどれだけ違うか表す）を求めるためのアルゴリズムを以下のページで見つけたのだが、よくわからないままプログラムだけを動かしていた。動的計画法そのものはとてもシンプルなもので、テキストを読んだらすんなり（ともいかないけどそこそこに）理解することができた。
レーベンシュタイン距離 - Wikipedia

おかげで編集距離だけではなく、置換した位置やどの文字が抜けていたか、どの文字がいらなかったかも調べられそうである。理解が進むとちょっと嬉しいが、このアルゴリズムはゼミで発表するうちの前振りでしかない（汗）