区间 DP 常见建模技巧

将区间左右端点显式表现在 dp 状态定义里

例如说 dp[l][r]dp[l][r] 表示区间 [l,r][l,r] 内的某某状态，且通常需要小区间拼接成大区间。为了保证正确性，这种转移通常先枚举区间长度，然后再枚举左右端点。

dp[l,r]←F( [l,a1],[a1,a2],…[am,r] ),l≤a1≤a2⋯≤am≤r dp[l,r]\gets F\Big(\ [l,a_1],[a_1,a_2],\dots[a_m,r] \ \Big),l\le a_1\le a_2\dots\le a_m\le r

有的时候，也会省略掉一个端点，只保留 ll (or rr)。这种形式的 DP 通常是区间的特例，即 dp[i]dp[i] 代表 [i,n][i,n] 后缀或者 [1,i][1,i] 前缀。状态转移差不多就是

dp[i]←dp[j]+f( [i,j) ) dp[i]\gets dp[j]+f\Big(\ [i,j)\ \Big)