文字列は動的計画法で数え上げなどの題材とされることが多い。蟻本にもそれのページがある。
ここでは、蟻本にないはずの自分で見つけた知見を書く。
ここでは、蟻本にないはずの自分で見つけた知見を書く。
文字列の動的計画法のテーブルの定義
文字列の動的計画法のテーブルの定義は、dp[i]などをi文字目を使用した時の〇〇〇〇、とするとうまくいきやすい！
蟻本にある例だけど、LCSの動的計画法のテーブルの定義も、dp(i, j) := Sのi文字目とTのj文字目まで使った時の最長であり、dp(k, l)(1 <= k <= i ,1 <= l <= j)までのすべてのベスト、という着眼点よりはこの定義の方がうまくいきやすいと思う。
最も、LCSの場合は前者は後者を含み、蟻本もその前提に立ってコードを書いてる。後者のような考え方を取らない場合は、二次元累積和配列を用意する必要がある。
認識としては、前者が普通で、LCSがたまたま後者にしても問題ない上に実装が楽になった、と考えたい。
認識としては、前者が普通で、LCSがたまたま後者にしても問題ない上に実装が楽になった、と考えたい。
例 ABC130 E(500) Common Subsequence
この場合、
dp(i, j) := Sのi文字目、Tのj文字目を最後尾として作れる共通部分列の場合の数
とするとうまくいく。動的計画法では珍しく、その状態のみをピンポイント指し、それ以外を含むということはない。
遷移としては、S(i) != T(j)は当然０となる。S(i) == T(j)ならば、dp(a, b)(ただし、a, bはそれぞれi - 1, j - 1まで計(i - 1) * (j - 1)通りすべて)の総和となる。これはSのi - 1文字目,Tのj - 1文字目までのすべての部分列と定義できる。それに最後にSもTにもあるS[i]とT[j]を足せば、新しい文字列となる。
また、今までの文字列を採用せず、S[i]のみで構成することも可能で、これは1通り。
之の実装で、上記の二次元累積和を使用すれば高速に更新できるので、この定義特有のデータ更新時のデータ取得の難しさを解決できる。
dp(i, j) := Sのi文字目、Tのj文字目を最後尾として作れる共通部分列の場合の数
とするとうまくいく。動的計画法では珍しく、その状態のみをピンポイント指し、それ以外を含むということはない。
遷移としては、S(i) != T(j)は当然０となる。S(i) == T(j)ならば、dp(a, b)(ただし、a, bはそれぞれi - 1, j - 1まで計(i - 1) * (j - 1)通りすべて)の総和となる。これはSのi - 1文字目,Tのj - 1文字目までのすべての部分列と定義できる。それに最後にSもTにもあるS[i]とT[j]を足せば、新しい文字列となる。
また、今までの文字列を採用せず、S[i]のみで構成することも可能で、これは1通り。
之の実装で、上記の二次元累積和を使用すれば高速に更新できるので、この定義特有のデータ更新時のデータ取得の難しさを解決できる。
例 ABC141 E(500) Who Says a Pun?
この問題自体は、ローリングハッシュ、Z-algorithmでも解ける。それは次のページを参照してほしい。
ローリングハッシュ
Z-algorithm
この問題の計算量は2乗を許容しており、これを考えると、DPを少し考えたくなる。上の内容を踏まえたDPを考えると、次のような定義を思いつく。
dp(i, j) := i番目文字とj番目の文字を最後尾としたときの連続部分列の長さの最大
これを思いつけば更新式も難しくはない。
dp(i, j) = 0 (if S[i] != S[j])
= min(dp(i - 1, j - 1) + 1, j - i)
dp(i, j) = 0 (if S[i] != S[j])
= min(dp(i - 1, j - 1) + 1, j - i)
最後のminの意味は、これはあくまで[i, j]の範囲内での連続部分列の最大の長さであり、長さをj - iに最大でも抑える必要がある。
次のように、
次のように、
aaaaaaaaaaaaaa
^ ^
| |
i j
でも、その添え字ではj - i個の長さまでしか見ておらず、最終的な答えに相当するもっと長いのはほかのもっとj - i大きい区間のDPの計算でわかる。
