問題名:Common Subsequence (PKU) 出典:Southeastern Europe 2003 難易度:☆☆☆ 問題の種類:DP 解法:LCS (Longest Common Subsequence) 解答ソースコード: 1458-deq.cpp アルゴリズムの概略 DPの四天王(?),LCS (Longest Common Subsequence) そのままの問題です。 アジア地区予選など,通常はこれをひねった問題が出てきます。 LCSとは,二つの値の列(この問題では文字列)が与えられて,最長の共通部分列を見つける問題です。 部分列は連続している必要はありませんが,順序は変更してはいけません。 例えば X = "abcfbc", Y = "abfcab" であればLCSは "abfc" や "abcb" になります。 LCSは一般的に複数ありえますが,この問題ではその長
![Common Subsequence 解説](https://cdn-ak-scissors.b.st-hatena.com/image/square/6e213cb4eb174290ce87ff504748524707bd7859/height=288;version=1;width=512/http%3A%2F%2Fwww.deqnotes.net%2Facmicpc%2F1458%2Flcs-anno1.png)