区間$[l, r)$を定義域とする動的計画法
<img src="https://gyazo.com/c26ccf2850d1bbdee5d71cea1c3bc249/thumb/1000" alt="image">
<ul>
<li>どう求めるかに何パターンかある(組み合わせて使うこともある)
</li>
<li>1: <a href="/ja/%E7%B8%AE%E3%82%81%E3%82%8B%E5%8C%BA%E9%96%93DP">縮める区間DP</a>
<ul>
<li>f(l, r)をf(l + 1, r)とf(l, r - 1)から求める</li>
</ul>
</li>
<li>2: <a href="/ja/%E4%B8%AD%E5%89%B2%E3%82%8A%E3%81%99%E3%82%8B%E5%8C%BA%E9%96%93DP">中割りする区間DP</a>
<ul>
<li>f(l, r)をf(l, i)とf(i, r)から求める (l &lt; i &lt; r)</li>
<li>O(N^3)になる<ul>
<li>間に合わない時</li>
<li>フェニック木などで範囲和を高速化する</li>
</ul>
</li>
</ul>
</li>
<li>3: 列から条件を満たす列を取り除く回数
<ul>
<li>図は<a href="/ja/PAST5L">PAST5L</a>のもの<ul>
<li>条件を満たす3つの要素の並びを取り除くことができる</li>
<li>取り除く個数の最大化をしたい</li>
<li>1と2はやった上でそれに加えて3をやる</li>
<li>線で表現された区間が取り除かれた後、残った丸が条件を満たすパターン</li>
</ul>
</li>
</ul>
</li>
<li><a href="/ja/DP%20L">DP L</a>
</li>
<li><a href="/ja/DP%20N">DP N</a>
</li>
<li><a href="/ja/ARC108E">ARC108E</a>
</li>
<li><a href="/ja/%E5%8C%BA%E9%96%93%E3%81%AE%E5%89%8A%E9%99%A4">区間の削除</a>　<a href="/ja/%E5%8C%BA%E9%96%93%E3%81%AE%E9%99%A4%E5%8E%BB">区間の除去</a>
<ul>
<li><a href="/ja/PAST5L">PAST5L</a></li>
<li><a href="https://algo-logic.info/range-dp/">https://algo-logic.info/range-dp/</a></li>
</ul>
</li>
<li><a href="/ja/%E5%9B%9E%E6%96%87">回文</a>
</li>
</ul>
<a href="https://www.hamayanhamayan.com/entry/2017/02/27/152226">https://www.hamayanhamayan.com/entry/2017/02/27/152226</a>
<a href="https://www.hamayanhamayan.com/entry/2017/03/20/234711">https://www.hamayanhamayan.com/entry/2017/03/20/234711</a>