DPマッチングのプログラミング

質問

Perlで記述されたDPマッチングのプログラムが欲しくて以下のようなサイト

http://chalow.net/2007-01-22-4.html

でソースを見つけたのですが，その実行結果が別のサイトで見たDPマッチングの説明と食い違うところがあり，本当に正しい実行結果なのかわかりません．実行結果は以下の通りで,同様の結果はWebサイトにも載っています

#foosurgerybar と survey を比較
% ./dp.pl
_ _ f o o s u r g e r y b a r
_ 0 0 0 0 0 0 0 0 0 0 0 0 0 0
s 1 1 1 1 0 1 1 1 1 1 1 1 1 1
u 2 2 2 2 1 0 1 2 2 2 2 2 2 2
r 3 3 3 3 2 1 0 1 2 2 3 3 3 2
v 4 4 4 4 3 2 1 1 2 3 3 4 4 3
e 5 5 5 5 4 3 2 2 1 2 3 4 5 4
y 6 6 6 6 5 4 3 3 2 2 2 3 4 5

具体的な疑問点としては，

・1行目（０が並んだ横行）と1列目（０～６が順番に並んだ縦列）は，一般的なDPマッチングの行列では生成されないのでは？

・スコアが５となっているが，どんなに少なく見積もってもスコアは７以上になるのではないか？（文字列長の差が７だから）

です．どなたかよろしくお願いいたします．

回答No.1

Tacosan

一番上の行と一番左の列は「プログラムの都合」(例えば「あった方がプログラムが簡単になる」など) で存在してるんだと思います.
で, そこでの「スコア」は「先頭や末尾にかたまって存在する『不一致部分』を無視する」ということになっていないかなぁ.