noshi91 https://blog.hatena.ne.jp/noshi91/ noshi91のメモ https://noshi91.hatenablog.com/ アルゴリズム を長さ の文字列とする。 の部分列が何種類あるか数え上げる。 DP 定義 の部分列であって で終わるものの種類数 の部分列の種類数 (空列含む) 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} \c… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fnoshi91.hatenablog.com%2Fentry%2F2023%2F02%2F26%2F135340" title="部分列 DP メモ - noshi91のメモ" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> Hatena Blog https://hatena.blog 2023-02-26 13:53:40 rich https://noshi91.hatenablog.com/entry/2023/02/26/135340 1.0 100%