定理 15.1 (LCS の部分構造最適性) は，最長共通部分列 (LCS) 問題が「最適部分構造」をもつことを示すものです。以下，定理の内容と具体例を通してその意味を解説します。
定理 15.1 の内容
文字列 $X = \langle x_1, x_2, \dots, x_m\rangle$ と
文字列 $Y = \langle y_1, y_2, \dots, y_n\rangle$ の LCS を $Z = \langle z_1, z_2, \dots, z_k\rangle$ とすると，次の３つの場合が成り立ちます。
-
末尾が一致する場合
$x_m = y_n$ ならば，必ず$$
z_k = x_m = y_n
$$かつ
$$
\langle z_1, \dots, z_{k-1} \rangle
\quad\text{は}
\quad
\mathrm{LCS}( \langle x_1,\dots,x_{m-1}\rangle,;\langle y_1,\dots,y_{n-1}\rangle )
$$となる。
-
末尾が不一致で，LCS の末尾が $X$ の末尾ではない場合
$x_m \neq y_n$ かつ $z_k \neq x_m$ ならば，
$Z$ は $\langle x_1,\dots,x_{m-1}\rangle$ と $Y$ の LCS。 -
末尾が不一致で，LCS の末尾が $Y$ の末尾ではない場合
$x_m \neq y_n$ かつ $z_k \neq y_n$ ならば，
$Z$ は $X$ と $\langle y_1,\dots,y_{n-1}\rangle$ の LCS。
これにより，文字列を末尾方向から「一文字ずつ削って考えれば」小問題に帰着できることがわかります。動的計画法で LCS を求める根拠がここにあります。
具体例で確認
以下の例で，各場合を確かめてみましょう。
- $X = \texttt{A B C B D A B}$
- $Y = \texttt{B D C A B A}$
これらの LCS のひとつは
$$
Z = \langle \texttt{B}, \texttt{C}, \texttt{B}, \texttt{A}\rangle
= \texttt{BCBA}
$$
（長さ 4）です。末尾同士を見てみます：
-
末尾一致の場合
$$
x_m = x_7 = \texttt{B},\quad y_n = y_6 = \texttt{A}
$$ここでは $\texttt{B}\neq\texttt{A}$ なので該当せず。
-
末尾不一致で $z_k \neq x_m$ の場合
-
$x_m=\texttt{B}$, $z_k=\texttt{A}$ なので確かに $z_k\neq x_m$。
-
このとき，定理より
$$
Z = \texttt{BCBA}
\quad\text{は}
\quad
\mathrm{LCS}(\langle\texttt{A B C B D A}\rangle,;Y)
$$すなわち $X$ の最後の文字 $\texttt{B}$ を除いた文字列と $Y$ の LCS であるはずです。
実際，
$$
X'=\texttt{A B C B D A},;Y=\texttt{B D C A B A}
$$に対しても LCS は長さ 4 の “BCBA” になり，定理どおりです。
-
-
末尾不一致で $z_k \neq y_n$ の場合
同様に $y_n=\texttt{A}$, $z_k=\texttt{A}$ なので今回は $z_k = y_n$ であり該当せず。
末尾一致の例
別の例として，次のように末尾文字が一致する場合を見てみましょう。
- $X = \texttt{A B C A}$
- $Y = \texttt{B C A}$
ここで末尾は両方とも $\texttt{A}$ なのでケース 1 に該当します。
LCS は “BCA”（長さ 3）で，末尾の $\texttt{A}$ が共通末尾です。
定理によれば，
“BC” は
$\langle \texttt{A B C}\rangle$ と $\langle \texttt{B C}\rangle$ の LCS であるはず。
実際に両方の LCS は “BC”（長さ 2）で一致します。
まとめ
- 定理 15.1 は，LCS 問題の「最適部分構造」を保証するもの。
- 「末尾一致」「末尾だけ片方を捨てる」のいずれかで，問題を必ず小さくできる。
- これが動的計画法（テーブル計算）で LCS を効率的に求める理論的根拠となる。
具体例を通して確認すると，定理の３つのケースがいずれも成り立つことが直感的に理解できるはずです。
LCS を動的計画法で解く「第２段階」としては，問題を小さな部分問題に帰着させるための**再起的な漸化式（recurrence relation）**を定義します。以下のように説明できます。
1. 部分問題の定義
まず，長さ $i$ の接頭辞 $X[1..i]$ と，長さ $j$ の接頭辞 $Y[1..j]$ の LCS の長さを
$$
c[i][j] = \bigl|\mathrm{LCS}(X[1..i],,Y[1..j])\bigr|
$$
と定義します。最終的に求めたいのは $c[m][n]$ です。
2. 境界条件（ベースケース）
-
$i=0$ （空文字列と何か）の場合は共通部分列は空なので
$$
c[0][j] = 0 \quad(\forall j)
$$ -
同様に $j=0$ の場合も
$$
c[i][0] = 0 \quad(\forall i)
$$
3. 再起的な漸化式
文字 $x_i$ と $y_j$ の比較結果によって，次の２通りに場合分けします。
-
末尾文字が一致するとき（$x_i = y_j$）
末尾の１文字を共通部分列に含められるので，$$
c[i][j] = c[i-1][,j-1,] + 1
$$ -
末尾文字が不一致のとき（$x_i \neq y_j$）
いずれかの末尾文字をあきらめる（部分問題をひとつ短くする）ので，$$
c[i][j] = \max\bigl(c[i-1][j],;c[i][j-1]\bigr)
$$
まとめると，
$$
c[i][j] =
\begin{cases}
0, & i=0 \text{ または } j=0,\
c[i-1][j-1] + 1, & x_i = y_j,\
\max\bigl(c[i-1][j],,c[i][j-1]\bigr), & x_i \neq y_j.
\end{cases}
$$
4. なぜこの漸化式になるのか
- 一致する場合：最後の文字を共通列の末尾に付け足せる。
- 不一致の場合：両方の末尾を同時に捨てるわけにはいかないので，どちらか一方だけ捨てればいい。「どちらを捨てると LCS が長くなるか」を比べるために $\max$ をとる。
この再起的定義に従って，二重ループで $i=1..m$, $j=1..n$ を走査し，テーブル $c[i][j]$ を順次埋めていけば、最終的に $c[m][n]$ が求まり、かつ必要なら逆向きに復元して実際の LCS 文字列も得られます。
小さな例
たとえば
$$
X=\texttt{ABCBDAB},\quad Y=\texttt{BDCABA}
$$
を考えると，$i=3,j=2$ （$X[1..3]=\texttt{ABC}$, $Y[1..2]=\texttt{BD}$）では
-
末尾文字は $\texttt{C}$ vs. $\texttt{D}$ で 不一致 ⇒
$$
c[3][2] = \max\bigl(c[2][2],,c[3][1]\bigr)
= \max(1,,1) = 1.
$$
こうしてテーブルを埋めることで，最終的に $c[7][6]=4$（LCS “BCBA” など）となります。
以上が，第２段階における「再起的な解の漸化式」の説明です。
以下に，第３段階として動的計画法で LCS の長さを求める擬似コード（LCS-Length）と，なぜその実行時間が $O(mn)$ になるかを丁寧に説明します。ここで文字列の長さをそれぞれ $X$ が長さ $m$，$Y$ が長さ $n$ とします。
LCS-Length の擬似コード
LCS-Length(X[1..m], Y[1..n])
// c は (m+1)×(n+1) の配列（0..m, 0..n を使う）
for i ← 0 to m
c[i][0] ← 0
for j ← 0 to n
c[0][j] ← 0
for i ← 1 to m
for j ← 1 to n
if X[i] = Y[j] then
c[i][j] ← c[i−1][j−1] + 1
else
c[i][j] ← max( c[i−1][j], c[i][j−1] )
return c // c[m][n] が LCS の長さ
- 配列サイズ：行が $0,1,\dots,m$、列が $0,1,\dots,n$ の計 $(m+1)\times(n+1)$ 要素
- 境界初期化：どちらか一方が空文字列（長さ0）なら LCS 長さは 0
- 再帰から反復へ：前段階の漸化式を，二重ループで順番にテーブルに書き込む
実行時間解析
-
境界初期化のコスト
- $i=0$ を固定して $j=0..n$ を初期化：$n+1$ 回の代入
- $j=0$ を固定して $i=0..m$ を初期化：$m+1$ 回の代入
いずれも $O(m+n)$
-
メインの二重ループ
for i ← 1 to m for j ← 1 to n 【一定時間の操作】- 外側ループは $i=1,2,\dots,m$ の $m$ 回
- 内側ループは $j=1,2,\dots,n$ の $n$ 回
- 各ループの中身は文字比較
X[i] = Y[j]＋配列参照と代入、あるいは２つの数の比較と代入。いずれも $O(1)$
したがって，メインループ全体で要する基礎操作の総数は
$$
m \times n \times O(1) = O(mn).
$$ -
全体コスト
境界初期化 $O(m+n)$ とメインループ $O(mn)$ を合わせても，支配項は $O(mn)$ なので$$
\text{LCS-Length の時間計算量} = O(mn).
$$
空間利用について（おまけ）
- 上記コードでは $(m+1)\times(n+1)$ のテーブルを使うため，空間計算量は $O(mn)$
- 空間を $O(\min(m,n))$ に削減する工夫もありますが，まずはこの基本形で理解するのが標準です
まとめ
- コード：二重ループで漸化式をテーブルに書き込み
- 時間計算量：ループの反復回数が $m$ × $n$ 回で，各反復は定数時間 ⇒ $O(mn)$
- 動的計画法の典型例として，文字列長の積に比例した効率的アルゴリズムです。