アルゴリズムと計算量の問題

$X=x_1{x}_2{x}_3=\mathrm{ACG}$、$Y=y_1{y}_2{y}_3=\mathrm{CAG}$ とし、$D[i][j]$ を「$X$ の先頭 $i$ 文字を $Y$ の先頭 $j$ 文字に変換する最小コスト」とする。$c_{\mathrm{ins}}=1,c_{\mathrm{del}}=2,c_{\mathrm{sub}}=3$ なので、漸化式は
$$D[i][j]=\min (D[i-1][j]+2,D[i][j-1]+1,D[i-1][j-1]+3\cdot [x_i\ne y_j])$$
である（$[x_i\ne y_j]$ は $x_i\ne y_j$ のとき $1$、$x_i=y_j$ のとき $0$）。

初期値: 空文字列にするには全部削除するので $D[i][0]=2i$、空文字列から作るには全部挿入するので $D[0][j]=j$。
$$D[0][0]=0,D[1][0]=2,D[2][0]=4,D[3][0]=6,D[0][1]=1,D[0][2]=2,D[0][3]=3$$

$i=1$（$x_1=\mathrm{A}$）
- $j=1$（$\mathrm{C}$、不一致）: $\min (D[0][1]+2,D[1][0]+1,D[0][0]+3)=\min (3,3,3)=3$
- $j=2$（$\mathrm{A}$、一致）: $\min (D[0][2]+2,D[1][1]+1,D[0][1]+0)=\min (4,4,1)=1$
- $j=3$（$\mathrm{G}$、不一致）: $\min (D[0][3]+2,D[1][2]+1,D[0][2]+3)=\min (5,2,5)=2$

$i=2$（$x_2=\mathrm{C}$）
- $j=1$（$\mathrm{C}$、一致）: $\min (D[1][1]+2,D[2][0]+1,D[1][0]+0)=\min (5,5,2)=2$
- $j=2$（$\mathrm{A}$、不一致）: $\min (D[1][2]+2,D[2][1]+1,D[1][1]+3)=\min (3,3,6)=3$
- $j=3$（$\mathrm{G}$、不一致）: $\min (D[1][3]+2,D[2][2]+1,D[1][2]+3)=\min (4,4,4)=4$

$i=3$（$x_3=\mathrm{G}$）
- $j=1$（$\mathrm{C}$、不一致）: $\min (D[2][1]+2,D[3][0]+1,D[2][0]+3)=\min (4,7,7)=4$
- $j=2$（$\mathrm{A}$、不一致）: $\min (D[2][2]+2,D[3][1]+1,D[2][1]+3)=\min (5,5,5)=5$
- $j=3$（$\mathrm{G}$、一致）: $\min (D[2][3]+2,D[3][2]+1,D[2][2]+0)=\min (6,6,3)=3$

よって求める最小コストは $D[3][3]=3$ である。

実際、$\mathrm{ACG}$ の先頭に $\mathrm{C}$ を挿入して $\mathrm{CACG}$（コスト $1$）、$3$ 文字目の $\mathrm{C}$ を削除して $\mathrm{CAG}$（コスト $2$）とすれば、合計 $3$ で変換できる。なお、置換 $2$ 回（$\mathrm{A}\to \mathrm{C}$、$\mathrm{C}\to \mathrm{A}$）ではコスト $6$ かかる。

長さが等しい（どちらも3文字）ので、挿入と削除の回数は等しい。したがって、操作を1回以上使うなら、置換を1回以上使うか、削除と挿入を1回ずつ以上使うことになる。置換1回のコストは3、削除と挿入を1回ずつ使うコストは $2+1=3$ なので、どちらでもコストは3以上になる。X と Y は異なる文字列なので操作は必要であり、最小値は3以上である。

実際に3で達成できる。ACG から先頭の A を削除して CG にする（コスト2）。次に C と G の間に A を挿入して CAG にする（コスト1）。合計コストは3である。

検算として、動的計画法（編集距離の表）でも同じ値になる。挿入と削除だけを使う場合、最長共通部分列の長さは2（AG または CG）なので、コストは削除1回と挿入1回で $2+1=3$ になる。2文字とも置換する場合は $3+3=6$ で、これより大きい。

よって最小値は3である。