数え上げは数学的な規則性があまり見られない問題は動的計画法、もしくは数学と動的計画法の合わせ技でほとんど解ける。この際、詳しいことはDEGwerPDFにあるので省略する。でも、意外に思いつかないものをここに書く。
今までのじゃなくて、今のところだけのDP
動的計画法の基本的な配列設定として、ある状態までのすべての総和などが挙げられる。しかし、その考えを棄却することでとける問題もある。すなわち、ある状態においてのみのそれに対応するものである。
このような実装をするとき、総和という操作が遷移式に必要な場合、N次元累積和などが有効なテクニックだと思う。
例えば、二次元累積和の更新の式として、
S(i + 1, j + 1) = S(i + 1, j) + S(i, j + 1) - S(i, j) + value(i, j)
を利用することができる。
このような実装をするとき、総和という操作が遷移式に必要な場合、N次元累積和などが有効なテクニックだと思う。
例えば、二次元累積和の更新の式として、
S(i + 1, j + 1) = S(i + 1, j) + S(i, j + 1) - S(i, j) + value(i, j)
を利用することができる。
ちなみに、このタイプのDPテーブルの定義は非常に文字列と相性がいい。
下の類題は↑のページにも載せる。
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通り。
之の実装で、上記の二次元累積和を使用すれば高速に更新できるので、この定義特有のデータ更新時のデータ取得の難しさを解決できる。
