部分列 DP ($O(\sigma N)$)
(DP/subsequence_dp.py)

• View this file on GitHub
• Last update: 2022-07-30 20:30:51+09:00

概要

小文字英字列 $S$ に対して部分列の通り数を求めるアルゴリズム。$\mathrm{nxt}$ 配列を使うことで数え上げの重複を防ぐのがポイント。

$\mathrm{nxt}$ 配列定義

$\mathrm{nxt}[i][j] :=$ $S$ の $i$ 文字目以降で初めて $\mathrm{chr}(j + 97)$ が登場するときのインデックス (すべて $1$-indexed)

状態遷移

状態を $\mathrm{dp}[i] :=$ $S$ の部分列で $i$ 文字目を最後に使用するときの通り数、とする。このときの遷移式は以下の通りとなる。

\(\mathrm{dp}[0] = 1\) \(\mathrm{dp}[\mathrm{nxt}[i][j]]\mathrel{+}=dp[i]\)

使い方

• calc_next(small_characters: Sequence) -> List[List[int]]
  長さ $N$、文字種類数 $\sigma = 26$ の小文字英字列 small_characters について、 $\mathrm{nxt}$ 配列を返す。計算量 $O(\sigma N)$

• subsequence_dp(small_characters: Sequence, MOD: int) -> int
  長さ $N$、文字種類数 $\sigma = 26$ の小文字英字列 small_characters について、部分列の通り数を $\mathrm{MOD}$ で割った余りを返す。計算量 $O(\sigma N)$

参考

部分列 DP — 文字列の部分文字列を重複なく走査する DP の特集

Verified with

• TestCase/unittest/subsequence_dp.unittest.test.py

Code

def calc_next(small_characters):
    n = len(small_characters)
    nxt = [[-1] * 26 for i in range(n + 1)]

    for i in reversed(range(n)):
        for val in range(26):
            if val == ord(small_characters[i]) - 97:
                nxt[i][val] = i + 1
            else:
                nxt[i][val] = nxt[i + 1][val]
    return nxt


def subsequence_dp(small_characters, MOD):
    n = len(small_characters)
    nxt = calc_next(small_characters)
    dp = [0] * (n + 1)
    dp[0] = 1

    for i in range(n):
        for val in range(26):
            if nxt[i][val] == -1:
                continue
            dp[nxt[i][val]] += dp[i]
            dp[nxt[i][val]] %= MOD

    ans = 0
    for i in range(n + 1):  # 空文字 (i = 0 のとき) も含める。
        ans += dp[i]
        ans %= MOD
    return ans

Traceback (most recent call last):
  File "/opt/hostedtoolcache/Python/3.12.4/x64/lib/python3.12/site-packages/onlinejudge_verify/documentation/build.py", line 71, in _render_source_code_stat
    bundled_code = language.bundle(stat.path, basedir=basedir, options={'include_paths': [basedir]}).decode()
                   ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/opt/hostedtoolcache/Python/3.12.4/x64/lib/python3.12/site-packages/onlinejudge_verify/languages/python.py", line 96, in bundle
    raise NotImplementedError
NotImplementedError

Back to top page