區間DP

施工中

介紹

在區間上做DP，通常複雜度都是 $N^2,N^3$ 有時候可以搭配莫名其妙的四邊形優化。

用遞迴寫會異常好寫

例題

先來些經典題

1. 石子合併 最經典題，但是要搭配斷環成鍊(也就是複製然後接兩倍)

2. n個矩陣相乘最少次數

3. 最優三角剖分

4. 105全國賽 pD

再來一些比較難一點點的題目

1. 105全國賽pD變化

2. CF149D 特殊的轉移方式

3. [IOI1998] Polygon

4. 2020 ICPC Asia Taipei-Hsinchu Regional pE

5. Blocks