最長共通部分列問題
入力列の個数が任意である一般の場合については、この問題はNP困難である。入力列の個数が一定のときには、この問題は動的計画法によって多項式時間で解く事ができる(後の項参照)。 N {\displaystyle N} 個の列があり、長さが n 1 , . . . , n N {\displaystyle n_{1},...,n_{N}} であるとする。単純な探索では、最初の列の 2 n 1 {\displaystyle 2^{n_{1}}} 個の部分列が残りの列の部分列であるかを確かめる。それぞれの配列は、残りの配列長の線形時間で評価される。それゆえ、このアルゴリズムの計算時間は、下記の通りである。
O ( 2 n 1 ∑ i > 1 n i ) . {\displaystyle O\left(2^{n_{1}}\sum _{i>1}n_{i}\right).}
2つの配列で列の長さが n と m の場合、動的計画法の解法による時間計算量は、O(n × m)である。
最長共通部分列問題は、部分構造最適性を持つ。すなわち、この問題は、簡単な部分問題に分解することができ、それらはさらに簡単な部分問題に分解でき、そして最後には自明な問題に帰着される。またこの問題は、部分構造重複性を持つ。上位の部分問題を解く際には、しばしば下位の部分問題の解を再利用することになる。これら二つの特質を伴うこの問題は、動的計画法と呼ばれる手法で解決できる。動的計画法では、部分問題の解をその都度計算するのではなく、メモ化しておく。メモ化、すなわち、ひとつのレベルの部分問題の解をテーブルに格納して、次のレベルの部分問題が利用できるようにし、計算量を節約することが、この手続きには必要不可欠である(メモを取ることによく似ている所が、名前の由来である)。この解法を次に示す。