No Caffeine, No Life

プログラミング(主にPython)

AOJ ALDS1_10_C:最長共通部分列 (LCS: Longest Common Subsequence)  動的計画法

問題:

最長共通部分列 | アルゴリズムとデータ構造 | Aizu Online Judge

解説:

「普通の」アルゴリズムはこちら:

最長共通部分列問題 (Longest Common Subsequence) - naoyaのはてなダイアリー

が、下記にあるように、最長共通部分列の「長さ」だけを求めるならより高速なアルゴリズムがある:

最長増加部分列・最長共通部分列 [いかたこのたこつぼ]

いかたこさんの解説、詳しいなぁ…。

解答例:

 「普通の」アルゴリズム(ただし、これはオンラインジャッジ上TLEになる(pythonの場合):

いかたこさんに掲載されているアルゴリズム(そのまんま):