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

文字列 $Z$ から $0$ 個以上の文字を取り除き、残った文字を元の順に並べて得られる文字列を $Z$ の部分列という（取り除く文字は連続していなくてよい）。$2$ つの文字列の両方の部分列である文字列を共通部分列といい、共通部分列のうち長さが最大のものを最長共通部分列という。

$2$ つの DNA の塩基配列を表す文字列
$$X=\mathrm{AGCAT},Y=\mathrm{GACTA}$$
を比べる。$X$ の先頭から $i$ 文字目を $x_i$、$Y$ の先頭から $j$ 文字目を $y_j$ とし、$X$ の最初の $i$ 文字と $Y$ の最初の $j$ 文字の最長共通部分列の長さを $L[i][j]$ とする（$0\le i\le 5,0\le j\le 5$）。$L[i][j]$ は $L[0][j]=L[i][0]=0$ と、$i,j\ge 1$ に対する漸化式
$$L[i][j]=\{\begin{array}{ll}L[i-1][j-1]+1& (x_i=y_j)\\ \max (L[i-1][j],L[i][j-1])& (x_i\ne y_j)\end{array}$$
で求められる。この表を埋めて、$X$ と $Y$ の最長共通部分列の長さ $L[5][5]$ を求めよ。

文字列 $Z$ から $0$ 個以上の文字を取り除き、残った文字を元の順に並べて得られる文字列を $Z$ の部分列という（取り除く文字は連続していなくてよい）。$2$ つの文字列の両方の部分列であるものを共通部分列といい、共通部分列のうち長さが最大のものを最長共通部分列という。

$2$ つの DNA 塩基配列を表す文字列
$$X=\mathrm{GATCA},Y=\mathrm{TACGA}$$
の最長共通部分列の長さを求めよ。

次の $4$ 個の品物から、重さの合計が $8$ 以下になるようにいくつか選ぶ。各品物は選ぶか選ばないかのどちらかで、同じ品物を $2$ 個以上選ぶことはできない。

品物を A, B, C, D の順に $1,2,3,4$ 番目とし、$i$ 番目の品物の重さを $w_i$、価値を $v_i$ とする。$V[i][w]$ を「$1$ 番目から $i$ 番目までの品物だけを使い、重さの合計が $w$ 以下になるように選んだときの価値の合計の最大値」とすると、$V[0][w]=0$ であり、$i\geqq 1$ のとき
$$V[i][w]=\{\begin{array}{ll}V[i-1][w]& (w<w_i)\\ \max \left(V[i-1][w],V[i-1][w-w_i]+v_i\right)& (w\geqq w_i)\end{array}$$
が成り立つ。この表を $w=0,1,\dots ,8$ について埋め、選んだ品物の価値の合計の最大値 $V[4][8]$ を求めよ。

文字列 $X$ から $0$ 個以上の文字を取り除き、残った文字を順序を変えずに並べた文字列を $X$ の部分列という。$2$ つの文字列 $X,Y$ の両方の部分列である文字列を共通部分列といい、共通部分列のうち長さが最大のものを最長共通部分列という。

$$X=\mathrm{CABDAB},Y=\mathrm{ABCADB}$$

とする。$X$ と $Y$ の最長共通部分列は、文字列として何通りあるか求めよ。ただし、取り出す文字の位置が異なっても、文字列として同じものは $1$ 通りと数える。

文字列 $Z$ から $0$ 個以上の文字を取り除き、残った文字を元の順に並べて得られる文字列を、$Z$ の部分列という（取り除く文字は連続していなくてよい）。

$2$ つの文字列
$$X=\mathrm{DBACBAD},Y=\mathrm{ABDCADB}$$
を考える。$X$ と $Y$ がどちらも $Z$ の部分列となるような文字列 $Z$（$X$ と $Y$ の共通超列）のうち、長さが最小のものの長さを求めよ。