アルゴリズム1000本ノック #3. Longest common subsequence - Qiita

Solution これも有名なDPの問題の1つです. 個人的にはめちゃくちゃ難しいと思います…. Longest Common Substringと似ていますが, 必ずしも要素同士は隣り合っている必要がないという点が異なります. 問題の例について考えてみます. 与えられた２つの文字列を縦と横に置いて, 下の図のようなテーブルを考えます. 例えばオレンジ色のセル Table[4][2] は S1.subString(0, 5) = "12245" と S2.subString(0, 3) = "692"の最長共通部分の長さを格納することになります. この問題を解くということは, この表のすべての値を埋めることと同一です. 0行目, 0列目から考えます. 例えば0行目, これは "1224533324" は "6" を含むか? "6" を見つけるまでは "0" を, もし見つけたら以降は "1