interval DP

Picture a row of items — beads on a string, characters in a word, walls along a fence — and a job you can only finish by repeatedly merging or splitting neighbouring pieces. Whatever you do, you always end up working on a contiguous stretch of the row, never a scattered handful. Interval DP is the pattern for exactly these problems: the thing you remember a partial answer about is a segment from position i to position j, written dp[i][j], and you build up answers for short segments first and long segments later.

The state dp[i][j] usually means the best cost (or count) of solving the sub-row covering positions i through j. The transition picks a split point: dp[i][j] is built from a smaller-left piece dp[i][k] and a smaller-right piece dp[k+1][j], plus the cost of joining them, minimized (or summed) over every legal split k between i and j. The key insight that makes this correct is optimal substructure: once you decide where the final merge happens, the two sides are independent sub-rows you can solve on their own. Because every sub-row is shorter than [i, j], you fill the table by increasing length — all intervals of length 1, then length 2, and so on — so every dp[i][k] and dp[k+1][j] is ready before you need it. A typical loop is: for len from 2 to n, for i, set j = i + len - 1, then take the best over k from i to j-1 of dp[i][k] + dp[k+1][j] + cost(i, k, j).

With n positions there are about n^2 / 2 intervals and each tries up to n split points, so the plain version costs O(n^3) time and O(n^2) space. That is fine for a few hundred positions and is the home of classics like matrix-chain multiplication and the optimal binary search tree. When the cost function is nicely behaved, the Knuth-Yao quadrangle inequality can shave the inner split search down and drop the whole thing to O(n^2). The common mistake is letting the two sides overlap or share the split element twice; be careful whether the merge point belongs to the left piece, the right piece, or neither.