部分列 DP メモ - noshi91のメモ

$S$ を長さ $n$ の文字列とする。 $S$ の部分列が何種類あるか数え上げる。

DP 定義

$\text{dp} \lbrack i \rbrack \lbrack c \rbrack : = ( S _ 0, S _ 1, \dots, S _ {i - 1} )$ の部分列であって $c$ で終わるものの種類数

$\text{sum} \lbrack i \rbrack : = ( S _ 0, S _ 1, \dots, S _ {i - 1} )$ の部分列の種類数 (空列含む)

DP 遷移

\begin{align} \text{dp} \lbrack i + 1 \rbrack \lbrack c \rbrack &= \begin{cases} \text{sum} \lbrack i \rbrack & \quad ( S _ i = c ) \cr \text{dp} \lbrack i \rbrack \lbrack c \rbrack & \quad ( S _ i \neq c ) \end{cases} \cr \text{sum} \lbrack i + 1 \rbrack &= 1 + \sum _ {c} \text{dp} \lbrack i + 1 \rbrack \lbrack c \rbrack = 2 ~ \text{sum} \lbrack i \rbrack - \text{dp} \lbrack i \rbrack \lbrack S _ i \rbrack \end{align}

$S _ i \neq c$ のケースは自明。 $S _ i = c$ の場合、 $c$ で終わる部分列は $i$ 文字目を使用するものだけを数えても問題ない。 $i$ 文字目を使用する部分列の種類数は、 $( S _ 0, S _ 1, \dots, S _ {i - 1} )$ の部分列の種類数である。

$\text{sum} \lbrack i + 1 \rbrack = 2 ~ \text{sum} \lbrack i \rbrack - \text{dp} \lbrack i \rbrack \lbrack S _ i \rbrack$ は式変形で導いても良いし、 $i$ 文字目を使うものと使わないもので $2 ~ \text{sum} \lbrack i \rbrack$ 個の部分列が考えられ、 $S _ i$ で終わる部分列のうち $i - 1$ 文字目まででも作れるもの $\text{dp} \lbrack i \rbrack \lbrack S _ i \rbrack$ 個が重複していると考えても良い。

実装例

https://judge.yosupo.jp/submission/127770