動的計画法.html

<!-- 全体的に何も説明できてない感がとてもある…、参考問題が必要 -->
<title>動的計画法</title>
<h2>基本</h2>
<p>
    問題を部分問題に分割して再帰的に解くことができるとしよう。
    そのとき部分問題が重複する場合、部分問題の答えを"メモ"することで、
    全体として重複なしの部分問題の個数のオーダーで問題を解ける。<br>
    このようなパラダイムを「動的計画法」(Dynamic Programming, DP)と呼ぶ。
</p>

<h2>様々なDP</h2>

<h3>多項式で表せるDP</h3>
<p><a href='http://yukicoder.me/wiki/polynomial_techniques'>多項式を使うテクニックたち</a>参照。</p>

<h3>特殊なグラフ上</h3>
<h4>グラフのtree width, 特にpath widthが小さい場合</h4>
<p>
    この場合、"境界"の頂点の情報だけを持てばいいことがある。
    $W$×$H$のグリッドはpath widthが$\min(W,H)$であり、様々な変種も含めよく用いられる。
</p>

<h4>連結性</h4>
<p>
    解の条件として連結性が要求される場合、その情報を持つ必要がある。これには頂点の分割の情報を持てばよい。
    グラフの tree width, path width が小さい場合、"境界"の連結性情報だけを持てばよい。
    ちなみに、この場合単純には$O^*(c^{O(w \log w)})$時間かかるが$O^*(c^{O(w)})$時間にできることがある(ただし実用的かどうかは別)。
</p>

<h3>その他</h3>
<h4>総和の総和</h4>
<p>
    「ある条件を満たす配列の総和の総和を求めよ」などという場合、部分問題に対する"答え"として、本来の答えの「総和の総和」に加え「条件を満たす個数」を同時に持つ必要がある。
    これは自然に多項式に一般化できるだろう。
</p>

<h4>文字列マッチング状態</h4>
<p>
    KMPやAho-Corasickによるパターンマッチングオートマトンの状態を状態として持つことで、文字列にマッチングできる。
    KMPの実装の1つやAho-Corasickの場合、状態遷移の最悪時間は線形時間となってしまうので、場合によってはそれをメモしてやる必要がある。
</p>

<h4>部分列を重複なしに数える</h4>
<p>
    うまく重複を"引いて"やる必要がある。
</p>

<h3>その他競技プログラミング界隈で用いられる用語</h3>
<h4>ビットDP</h4>
<p>集合の要素2^Nの状態を持つ場合、整数により表現するとビット演算で集合演算ができる。そのような状態を持つDP。</p>
<h4>木DP</h4>
<p>木の問題に対するDP。</p>
<h4>区間DP</h4>
<p>区間を状態として持つDP。</p>
<h4>桁DP</h4>
<p>数値の"桁"(位取り記数法でいう「位」)を状態として持つDP。</p>
<h4>ゲームDP</h4>
<p>2人ゲームのDP。単純に勝ちを判定する場合やmin-maxをする場合など。</p>

<h2>テクニック</h2>
<h3>データ構造などを用いた遷移の高速化</h3>
<p>
    どんなデータ構造でも目的さえ合っていれば使える。
    静的なデータに対するクエリやオフラインクエリができれば十分なことが多い。
</p>
<h4>累積和法</h4>
<p>
    数え上げの問題などでは累積和法やその逆を用いることができることがある。配るDPでもできる。
</p>
<h4>Convex-hull trick</h4>
<p>
    線形多項式のminを取るような遷移などを高速化できる。
</p>
<h3>遷移が線形の場合</h3>
<p>
    遷移を行列とみなし行列累乗をすることで高速化できることがある。
    この場合半環であればよいので、数え上げの問題の他にも最小化・最大化の問題にも使える。
</p>
<h4>畳み込み</h4>
<p>
    $O(n^2)$時間での畳込みやFFTを用いた$O(n \log n)$時間の畳込みが使えることがある。
</p>
<h3>その他</h3>
<h4>メモリ節約</h4>
<p>
    うまく実装すればメモリを節約できることがある。
    メモリの節約は実行速度の高速化につながることもあるため、重要である。
</p>
<h4>単調性のあるboolean DP</h4>
<p>
    答えとしてboolを取るDPにおいて単調性がある場合、その境界を整数で保持するだけで十分であり、高速化になる。
</p>

<h2>参考記事</h2>
<ul>
<li><a href='http://www.slideshare.net/iwiwi/ss-3578511'>プログラミングコンテストでの動的計画法</a></li>
<li><a href='http://d.hatena.ne.jp/Tayama/20111210/1323502092'>DPの話</a></li>
</ul>