Interval DP and O(n³) algorithms

Many problems ask: optimize over all possible ways to partition a sequence. If you try every partition, the number of possibilities explodes. But if each partition overlaps only with parts you have already solved, dynamic programming lets you compute the answer in polynomial time.

Interval DP defines a subproblem for each contiguous interval of the sequence. The state is an interval [i, j]. The solution for [i, j] is built from solutions on smaller intervals that overlap [i, j].

The recurrence structure

For an interval [i, j], try all split points k where i <= k < j. The interval splits into [i, k] and [k + 1, j]. Compute the optimal answer on each part, then combine them.

def solve(dp, cost, i, j):    return min(dp[i][k] + dp[k + 1][j] + cost(i, k, j)               for k in range(i, j))

The cost term depends on the problem. It might be the cost to merge the two parts, or the cost of a transition between them.

Compute the table bottom-up by increasing interval length: first all length-1 intervals (single elements), then length 2, then length 3, and so on. When you compute dp[i][j], all smaller intervals are already known.

An example: merging intervals

You have a sequence of n numbers. Merging two adjacent elements costs the sum of their values. Merging all into one sequence has a total cost. Find the minimum cost.

If you merge elements 0 and 1, you get a new element with value s[0] + s[1]. If you then merge this with element 2, you pay (s[0] + s[1]) + s[2]. Different merge orders give different costs.

This is the classic optimal merge cost problem. The solution is an interval DP where dp[i][j] is the minimum cost to merge all elements in the range [i, j] into a single element. The cost to merge two parts [i, k] and [k+1, j] is dp[i][k] + dp[k+1][j] + prefix_sum[j+1] - prefix_sum[i].

1import sys2
3
4def main() -> None:5    input_data = sys.stdin.read().split()6    if not input_data:7        return8
9    idx = 010    n = int(input_data[idx])11    idx += 112
13    arr = []14    for _ in range(n):15        arr.append(int(input_data[idx]))16        idx += 117
18    prefix = [0] * (n + 1)19    for i in range(n):20        prefix[i + 1] = prefix[i] + arr[i]21
22    dp = [[0] * n for _ in range(n)]23
24    for length in range(2, n + 1):25        for i in range(n - length + 1):26            j = i + length - 127            dp[i][j] = float('inf')28
29            for k in range(i, j):30                cost = dp[i][k] + dp[k + 1][j] + (prefix[j + 1] - prefix[i])31                dp[i][j] = min(dp[i][j], cost)32
33    sys.stdout.write(str(dp[0][n - 1]) + "\n")34
35
36if __name__ == "__main__":37    main()

4
2 3 5 7

32

The program computes dp[i][j] by increasing interval length. For a single element, the cost is 0. To merge an interval, try every split point and take the minimum.

Why interval DP works efficiently

The number of intervals is O(n²), and you can compute each interval once if you process them in the right order. If you compute by increasing interval length, all smaller intervals are ready when you need them. The recurrence tries all split points (O(n) of them), so the total time is O(n³).

Without DP, trying all partitions of a sequence creates 2^n possibilities, which is infeasible. With DP, you avoid recomputing overlapping subproblems. The constraint that you split at a single position reduces the problem space dramatically.

A second example: matrix chain multiplication

Suppose you have four matrices A, B, C, D with dimensions 10×20, 20×30, 30×40, and 40×10. Multiplying matrix of size (p×q) with matrix of size (q×r) costs p×q×r scalar multiplications.

To compute A×B×C×D, you can parenthesize it as (A×B)×(C×D) or ((A×B)×C)×D or other ways. The total scalar multiplication count depends on the parenthesization.

Define dp[i][j] as the minimum number of multiplications to compute the product of matrices from index i to j. For two matrices, dp[i][i+1] = dimensions[i] × dimensions[i+1] × dimensions[i+2].

For a longer chain, try splitting at each position k. Multiply matrices [i, k] (cost dp[i][k]), then matrices [k+1, j] (cost dp[k+1][j]), then the two results (cost dimensions[i] × dimensions[k+1] × dimensions[j+1]). The total is dp[i][k] + dp[k+1][j] + dimensions[i] × dimensions[k+1] × dimensions[j+1]. Take the minimum over all k.

This is structurally identical to the merging example, showing that interval DP applies to many different problems.

Optimization: monotonicity

The basic interval DP is O(n³): n² intervals, and each tries O(n) split points. For some problems, the optimal split point for [i, j] is always between the optimal split points for [i, j-1] and [i+1, j]. This is the monotonicity property.

With monotonicity, use a divide-and-conquer approach instead of trying all split points. Compute intervals by optimal split position, not interval length. For each position, binary search or use two pointers to find the optimal k. This reduces the time to O(n² log n) or O(n²).

Without monotonicity, you need all O(n³) time. Check the problem constraints to decide if optimization is necessary.

Common mistakes

One mistake is to compute the table top-down without memoization, then recompute the same interval many times due to overlapping subproblems. Always use a bottom-up table or explicit memoization to ensure each interval is computed exactly once. Without this, the algorithm degrades to exponential time.

Another mistake is to forget the base case or initialize the table incorrectly. An interval of length 1 has a specific cost (often 0, but sometimes the value itself). If the base case is wrong, all larger intervals propagate the error. Double-check: what does dp[i][i] represent, and what is its value?

A third mistake is to confuse the cost function and what is being optimized. Some problems ask for the minimum cost to build or merge. Others ask for the maximum or the count. Some ask for the cost to partition or break. Read the problem carefully to understand whether you are minimizing, maximizing, or counting, and what contributes to the cost at each merge or split point.

A fourth mistake is to process intervals in the wrong order. You must compute intervals of length 1 before length 2, length 2 before length 3, and so on. If you try a different order, you will reference DP values that have not been computed yet, leading to zeros or undefined values and incorrect results.

Recap

Interval DP defines subproblems on contiguous intervals. For each interval, try all ways to split it and combine the solutions. Compute the table bottom-up by increasing interval length. The basic algorithm is O(n³), but monotonicity or convex hull optimization can reduce this to O(n² log n) or O(n²) on certain problem classes. Interval DP solves many problems that seem to have exponentially many partitions.