Segment DP

aka segmentation dp

this is prefix dp as opposed to internal dp because we operate on prefixes ( rather than intervals — any arbitary split that is not a prefix )

a ggeneral sementation dp is optimising something over segments

$$\boxed{F(i,j)={\mathrm{opt}}_{j-1\le p<i}\left(F(p,j-1)+C(p+1,i)\right)}$$

is the general idea of a segmentation dp $C$ is the cost of adding a new sement from $p+1$ to $i$, and we then optimise over any $j-1$ count of segments in the prefix.

problems

max sum of k disjoin segments

problem: https://atcoder.jp/contests/abc466/tasks/abc466_e

the original problem was about flipping and maximising sum there, which can be modeled as $sum(a)+del$ where $d_i=b_i-a_i$ aka the gain on flip. Obvious to see that optimal solution will have disjoin ranges ( or can be represented using disjoin ranges ).

recurrence

Define $dp(i,j)$ as the maximum sum using exactly $j$ disjoint segments, where the last segment ends at $i$, so $v_i$ is taken.

There are two choices in the prefix

1. If the previous segment also ends at $i-1$, extend it:

$$dp(i-1,j)+v_i$$

2. If the previous segment ends at any earlier position $t<i$, start a new segment at $i$:

$$\underset{j-1\le t<i}{\max }dp(t,j-1)+v_i$$

Therefore,

$$dp(i,j)=\max \left(dp(i-1,j)+v_i,\underset{j-1\le t<i}{\max }dp(t,j-1)+v_i\right)$$

For one segment,

$$dp(i,1)=\max \left(dp(i-1,1)+v_i,v_i\right)$$

impl notes

• instead of going from $j-1$ to $i$, you can go from 0, it’s just that only $j-1$ would be valid since you can’t build $j$ segments without that many elements, but that can be cleanly skipped via a defaul value of $-inf$ and skipping states that read from such transition.
• the max over prefix you can compte as a prefix max at each step.
• if you needed exacly $k$ segments, you would use the max over the $dp(...,k)$. If you need atleast, you need to variate that k as well.