Dynamic programming with the interval $[l, r)$ as the domain of definition
<img src="https://gyazo.com/c26ccf2850d1bbdee5d71cea1c3bc249/thumb/1000" alt="image">
<ul>
<li>There are several patterns in how to ask for it (sometimes in combination).
</li>
<li>1: <a href="/en/Section%20DP%20to%20be%20shortened">Section DP to be shortened</a>
<ul>
<li>Find f(l, r) from f(l + 1, r) and f(l, r - 1)</li>
</ul>
</li>
<li>2: <a href="/en/Section%20DP%20to%20be%20divided%20into">Section DP to be divided into</a>
<ul>
<li>Find f(l, r) from f(l, i) and f(i, r) (l &lt; i &lt; r)</li>
<li>O(N^3).<ul>
<li>When you can&#39;t make it in time</li>
<li>Speed up range summation with phenic trees, etc.</li>
</ul>
</li>
</ul>
</li>
<li>3: Number of times to remove columns that satisfy the condition from the column
<ul>
<li>Figure from [PAST5L<ul>
<li>We can remove a sequence of three elements that satisfy the condition</li>
<li>I want to maximize the number of pieces to remove.</li>
<li>I&#39;ve done 1 and 2, and I&#39;ll do 3 in addition to that.</li>
<li>Pattern in which the remaining circles satisfy the condition after the section represented by the line is removed</li>
</ul>
</li>
</ul>
</li>
<li><a href="/en/DP%20L">DP L</a>
</li>
<li><a href="/en/DP%20N">DP N</a>
</li>
<li><a href="/en/ARC108E">ARC108E</a>
<ul>
<li><a href="/en/Deletion%20of%20a%20section">Deletion of a section</a> 　 <a href="/en/Section%20removal">Section removal</a></li>
<li><a href="/en/PAST5L">PAST5L</a></li>
<li><a href="https://algo-logic.info/range-dp/">https://algo-logic.info/range-dp/</a></li>
<li><a href="/en/palindrome">palindrome</a></li>
</ul>
</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>
<hr>
This page is auto-translated from <a href="https://scrapbox.io/nishio/%E5%8C%BA%E9%96%93DP">/nishio/区間DP</a> using DeepL. If you looks something interesting but the auto-translated English is not good enough to understand it, feel free to let me know at <a href="https://twitter.com/nishio_en">@nishio_en</a>. I&#39;m very happy to spread my thought to non-Japanese readers.

Interval DP