AtCoder Beginner Contest 130：E - Common Subsequence
問題
解法
まず，問題文の解釈から．選んだ部分列の数字を文字列を連結させて読むのではなく，数列としてみたときに等しいものの個数を求める．例えば {1, 3, 3, 3} と {1333} は，各項を文字列としてみて連結させると同じものになるが，数列としてコンマ区切りで見ると当然同じではない．
以下の DP を考える．
dp(i, j) := S_i, T_j までありうる共通の部分列の個数の和
遷移は
dp(i, j) = dp(i - 1, j) + dp(i, j - 1) - dp(i -1, j - 1) (S_i == T_j のとき + dp(i - 1, j - 1) を追加でする)
となる．- dp(i - 1, j - 1) をしているのは，dp(i - 1, j) と dp(i, j - 1) の中で dp(i - 1, j - 1) を重複して数えてしまっているため．全体で O(NM)．
解答
問題文の解釈を間違っていたため Virtual コンテスト中に解けなかった...
