ABC130 E - Common Subsequence - ツバサの備忘録

解法

LCSや編集距離に近いものを感じたので、似たような遷移のDPを考えていきます。

$dp[i][j] = S_{i},T_{j}$ までを見終えた段階でできる、問題の条件を満たす整数列の個数

とします。
初期値としては、 $dp[i][0] = dp[0][j] = 1$ です。いずれのパターンでも、 $S,T$ 共に1つも選ばない1通りの整数列のみです。
求めたい答えは、 $dp[n][m]$ に格納されています。
ということで遷移を考えていきます。
まずは、 $dp[i][j]$ の値を考えるとき、まずは $(S_{i},T_{j})$ のペアを部分列に使わないパターンを考えます。すると、
$S_{i},T_{j-1}$ までを見終えた段階でできる部分列の個数と、 $S_{i-1},T_{j}$ までを見終えた段階でできる部分列の個数を足せば基本的に網羅できそうな気がします。
が、この遷移をよく見てみると、 $dp[i][j-1],dp[i-1][j]$ どちらにも $dp[i-1][j-1]$ が足されているため、この部分を重複して数え上げてしまうことになります。
この重複を消す必要があるので、
$dp[i][j] = dp[i][j-1] + dp[i-1][j] - dp[i-1][j-1]$
となります。
あとは、 $(S_{i},T_{j})$ のペアを使って部分列を構成するパターンで、このパターンは、ちょうど $dp[i-1][j-1]$ 通りだけ存在します。
ということで、
$dp[i][j] = \left\{ \begin{array}{} dp[i][j-1] + dp[i-1][j] - dp[i-1][j-1]　(S_{i} \neq T_{j})\\ dp[i][j-1] + dp[i-1][j]　(S_{i} = T_{j}) \end{array} \right.$
となります。
あとはこの遷移を行うことで、答えを求めることができます。