LCS：最長共通部分列
2 つの文字列に共通して現れる「一番長い並び」を、表を 1 マスずつ埋めて求めます。
2 つの文字列（英字、最大 10 文字）
埋めるステップ
0
計算中
左上（一致）
上・左（不一致）
復元経路
LCS に採用した文字
—
部分列とは、元の文字列から文字を飛ばしながら順序を保って取り出した並び。
2 つの文字列に共通する部分列のうち最長のものが LCS です（DNA 比較・diff・文書の類似度などに使われます）。
表
・末尾の文字が一致 → 左上＋1（共通文字が 1 つ伸びる）
・一致しない → 上と左の大きい方（どちらかの末尾を捨てる）
表
dp[i][j] ＝「文字列 A の最初の i 文字、B の最初の j 文字での LCS の長さ」。・末尾の文字が一致 → 左上＋1（共通文字が 1 つ伸びる）
・一致しない → 上と左の大きい方（どちらかの末尾を捨てる）
いま計算しているマス
ここが DP の本質
- 「2 つの文字列全体の LCS」を 「先頭 i 文字 と 先頭 j 文字 の LCS」という部分問題に分解。
- 各マスは すでに埋めた近所 3 マス（左上・上・左）だけで決まる。指数的な総当たりが不要に。
- 表を埋めたら右下が答え。右下から左上へたどると LCS の中身（どの文字を選んだか）が復元できる。