Interval DP Introduction

Prerequisite: Dynamic Programming Introduction

Interval DP solves problems on subarrays or substrings where the answer for a range [l, r] depends on smaller ranges within it. The state dp[l][r] represents the answer for the subproblem covering indices l through r inclusive.

Identifying Interval DP Problems

Two signals indicate this pattern. First, the input is a linear sequence (array or string). Second, the problem requires considering all possible contiguous ranges, and solutions for larger ranges combine solutions from smaller ranges.

Common interval DP problems include matrix chain multiplication, optimal game strategies, palindrome partitioning, and merging stones. Constraints typically allow sequence lengths up to 500-1000, suggesting an O(n^2) or O(n^3) solution.

Example: Coin Game

Two players take turns picking coins from either end of a row. Each player plays optimally to maximize their score. Find the maximum score the first player can achieve.

State: dp[l][r] = maximum score difference (current player minus opponent) for coins in range [l, r]

Transition: The current player picks from either end, then the opponent plays optimally on the remaining range:

dp[l][r] = max(coins[l] - dp[l+1][r], coins[r] - dp[l][r-1])

The subtraction accounts for alternating turns: what's good for the opponent is bad for the current player.

Base case: dp[i][i] = coins[i] (single coin: take it)

Common Transition Patterns

Interval DP transitions typically examine smaller ranges within the current range. The two main patterns are element removal and interval splitting.

Element removal shrinks the range from one end. In the coin game, picking the left coin reduces [l, r] to [l+1, r]. Picking the right coin reduces it to [l, r-1].

Interval splitting divides the range at some point m. For matrix chain multiplication, dp[l][r] tries all split points: dp[l][m] + dp[m+1][r] + cost(l, m, r). This requires iterating over all possible m values, adding an O(n) factor to each state.

Top-Down: The Natural Choice for Interval DP

Interval DP is one case where top-down is often easier than bottom-up. The reason: you don't need to figure out the processing order.

With bottom-up, you must ensure smaller intervals are computed before larger ones. This requires the non-obvious "iterate by length" pattern. With top-down, the recursion handles dependencies automatically—when solve(l, r) needs solve(l+1, r), it just calls the function, which computes and caches the result.

from functools import lru_cache

def coin_game(coins):
    @lru_cache(maxsize=None)
    def solve(l, r):
        if l == r:
            return coins[l]  # Base case: take the only coin
        pick_left = coins[l] - solve(l + 1, r)
        pick_right = coins[r] - solve(l, r - 1)
        return max(pick_left, pick_right)

    return solve(0, len(coins) - 1)

The code reads exactly like the recurrence. No index manipulation, no worrying about which intervals to compute first.

Bottom-Up: Processing by Interval Length

If you prefer bottom-up or need to avoid recursion, you need to understand the state space and fill order.

The Two-Dimensional State Space

Unlike prefix-based DP where dp[i] considers elements 0..i, interval DP uses dp[l][r] to represent any contiguous range. For a sequence of length n, there are O(n^2) possible intervals, though only ranges where l <= r are valid (the upper triangle of the table).

Fill Order: By Increasing Length

Since larger intervals depend on smaller ones, process intervals in order of increasing length. Start with length 1 (base cases), then length 2, then length 3, up to length n. Within each length, iterate over all valid starting positions.

def coin_game(coins):
    n = len(coins)
    dp = [[0] * n for _ in range(n)]

    # Base case: single coins (length 1)
    for i in range(n):
        dp[i][i] = coins[i]

    # Fill by increasing length
    for length in range(2, n + 1):
        for l in range(n - length + 1):
            r = l + length - 1
            pick_left = coins[l] - dp[l + 1][r]
            pick_right = coins[r] - dp[l][r - 1]
            dp[l][r] = max(pick_left, pick_right)

    return dp[0][n - 1]

This guarantees that when computing dp[l][r], all smaller intervals like dp[l+1][r] and dp[l][r-1] are already computed.

Time and Space Complexity

Interval DP uses O(n^2) space for the 2D table. Time complexity depends on the transition. Element removal (constant work per state) yields O(n^2) total. Interval splitting (trying all split points) yields O(n^3) total.