アルゴリズムでエディットグラフについて題材があると思います。  (26年    秋)


それで質問なんですが、この問題において二次元配列を使っていると思いますが、
参考書や動画の解説では二次元配列を下から上に向かって埋めていくように思われます。

でも本来二次元配列って下から数えて0  1  2 と進んで行きますよね？
どうしてこの問題だけ下から  0 1 2 になるのでしょうか？

後すいません、忘れてました。

多くの解説では  例えば  D[ X , 0 ] ←  X   の部分を線分を作っているなどと解説されていますが、これはパターンが分かっているからであって、普通であればD[ X , 0 ] ←  X は
代入です。

こういう特殊なケースの場合解説部分はどう読み解けばいいですか？

すいません、何度も！
後    D[ X , 0 ] ←  X    でなぜ線がひけるのでしょうか？

後分岐の部分も  代入で斜め線が引けるのも謎です。



      

一番上の質問がよくわからないので
とりあえずD[ X , 0 ] ←  X と斜め線の意味だけ･･･

D[ X , 0 ] ←  X は代入で間違いありません。
0≦X＜Str1Len間のD[ X , 0 ]にXをそれぞれ代入しています。
グラフ上で説明すると原点(0,0)からの距離という風に捕らえることが出来ますので線分を描いているように見えるのです。

次に斜め線の意味は、
元々その位置にあったものをそのまま使いますよって意味です。
だから操作なしで編集距離0になるわけですね。

ざっくりした説明で申し訳ないですがだいたいこんな感じです

①最初の質問は誤入力があるようですが、質問の意図を考えて答えます。左下から出発して右上に行くので下から配列の番号が付けてあります。左上から出発して右下に行くなら上から番号を付ければよくて、どちらにしても解き方は同じです。
②説明では線を引くと書いてありますが、プログラムで線を引くわけではありません。アルゴリズムを考えるためで線があると考えるだけです。求めるのは距離だけです。D[X,0]←Xは前の投稿のように(0,0)から(X,0)までの距離を入力しています。(0,0)から(X,0)までの最短距離はXでしょう。斜めに進めるのはD[X,Y]=MIN(D[X-1,Y-1],D[X,Y-1],D[X-1,Y])にD[X-1,Y-1]があることです。(X-1,Y-1)にある文字が等しいと(Str1[X-1]=Str2[Y-1])),(X-1,Y-1)から(X,Y)に距離0で行けるから斜めに線が引かれているように考えるのです。