05 — Interval DP & Subsequence DP¶

Phase 4 | Week 27–28 | Feb 9 – Feb 15, 2027

This is the point where DP stops being approachable and starts being genuinely hard. Most people can handle the linear and knapsack patterns after enough practice. Interval DP and the harder subsequence problems require a fundamentally different kind of thinking — you’re no longer asking “what happened at the previous step?” but “what was the last thing to happen inside this entire range?” That inversion is not intuitive. Give this section more time than you think it needs.

Part I — Interval DP¶

The Interval DP Template¶

When it applies: Problems where you’re asked for the optimal answer over a contiguous subarray or subsequence [i, j], and the answer depends on answers to smaller intervals within [i, j].

State: dp[i][j] = optimal answer for the subproblem on range [i, j].

Template:

# Fill by increasing interval length
for length in range(2, n+1):         # interval length from 2 to n
    for i in range(n - length + 1):  # start of interval
        j = i + length - 1           # end of interval
        dp[i][j] = initial_value
        for k in range(i, j):        # split point
            dp[i][j] = optimize(dp[i][j], f(dp[i][k], dp[k+1][j]))

The key insight: You enumerate all possible “last operations” or “split points” k within [i, j]. Whatever k does — it splits the problem into two independent subproblems you’ve already solved.

Problem 1: Matrix Chain Multiplication¶

Problem: Given matrices M[0..n-1] where M[i] has dimensions p[i] x p[i+1]. Find the minimum number of scalar multiplications to compute the product of all matrices. Parenthesization matters: (AB)C can differ from A(BC) in cost.

State: dp[i][j] = minimum multiplications to compute M[i] × M[i+1] × … × M[j].

Transition: Try every possible last multiplication — split into (M[i]..M[k]) and (M[k+1]..M[j]):

for k in range(i, j):
    cost = dp[i][k] + dp[k+1][j] + p[i] * p[k+1] * p[j+1]
    dp[i][j] = min(dp[i][j], cost)

The p[i] * p[k+1] * p[j+1] term is the cost of multiplying the two resulting matrices together.

Base case: dp[i][i] = 0 (single matrix, no cost).

Answer: dp[0][n-1]

Fill order matters: Since dp[i][j] depends on dp[i][k] and dp[k+1][j] for k < j, all shorter intervals must be computed before longer ones. The outer loop over length handles this.

Problem 2: Burst Balloons¶

Problem: Given array nums of n balloons. Burst balloon i earns nums[i-1] * nums[i] * nums[i+1] coins (neighbors’ values). After bursting, i’s former neighbors become adjacent. Maximize total coins.

Why this is hard: Bursting changes the array structure — the “neighbors” of a balloon change as others are removed. Forward simulation doesn’t work cleanly.

The inversion: Think about the last balloon to burst in range [i, j], not the first. If k is the last balloon to burst in (i, j):

When k bursts, its neighbors are i and j (everyone else in the range is already gone)
The subranges (i, k) and (k, j) are completely independent

State: dp[i][j] = maximum coins from bursting all balloons strictly between index i and j (exclusive). We pad the array with nums[-1] = nums[n] = 1.

Transition:

for k in range(i+1, j):
    coins = dp[i][k] + nums[i] * nums[k] * nums[j] + dp[k][j]
    dp[i][j] = max(dp[i][j], coins)

Answer: dp[0][n+1] (bursting all balloons between the two padding 1s).

This is the paradigmatic example of the “last operation” inversion. If you understand why you think about the last balloon instead of the first, you understand interval DP.

Problem 3: Palindrome Partitioning II¶

Problem: Given string s, find the minimum number of cuts to partition it into palindromes.

Two-phase approach:

Precompute is_palindrome[i][j] for all pairs (O(n²) using expand-around-center or DP).
1D DP: dp[i] = minimum cuts for s[0..i].

Transition:

for i in range(n):
    if is_palindrome[0][i]:
        dp[i] = 0   # whole prefix is a palindrome, no cut needed
    else:
        dp[i] = min(dp[j-1] + 1 for j in range(1, i+1) if is_palindrome[j][i])

The interval DP precomputation is what makes this O(n²) rather than O(n³).

Part II — Subsequence DP¶

LIS — Longest Increasing Subsequence¶

Problem: Given array nums, find length of the longest strictly increasing subsequence.

O(n²) DP Solution¶

State: dp[i] = length of LIS ending at index i.

Transition:

for i in range(n):
    dp[i] = 1   # LIS ending here is at least the element itself
    for j in range(i):
        if nums[j] < nums[i]:
            dp[i] = max(dp[i], dp[j] + 1)

Answer: max(dp)

O(n log n) Solution — Patience Sorting¶

This is the solution you need to know. It’s the standard for any serious LeetCode Hard or competitive problem.

Idea: Maintain a “pile array” tails where tails[k] = smallest tail element of all increasing subsequences of length k+1.

Algorithm:

tails = []
for num in nums:
    pos = binary_search_left(tails, num)  # find leftmost position where tails[pos] >= num
    if pos == len(tails):
        tails.append(num)    # num extends the longest subsequence
    else:
        tails[pos] = num     # num replaces — doesn't extend, but improves future potential
return len(tails)

Why it’s correct: At any point, tails is sorted. len(tails) is the LIS length. The binary search replacement maintains the invariant that each tails[k] is the smallest possible tail for length k+1 — which maximizes future extension potential.

O(n log n): n elements, O(log n) binary search each.

LIS appears in problems about stock prices, patience sorting, and building nested structures. Recognize it, reach for the O(n log n) version immediately.

Longest Palindromic Subsequence¶

Problem: Find length of the longest palindromic subsequence in string s.

Key insight: LPS(s) = LCS(s, reverse(s)). Run LCS on s and its reverse.

Alternatively, define it directly:

State: dp[i][j] = length of LPS in s[i..j].

Transition:

if s[i] == s[j]:
    dp[i][j] = dp[i+1][j-1] + 2
else:
    dp[i][j] = max(dp[i+1][j], dp[i][j-1])

Fill by increasing interval length (interval DP pattern). Base: dp[i][i] = 1.

LIS Variants Worth Knowing¶

Number of LIS (LeetCode 673): Count how many distinct LIS exist. Requires tracking both dp_len[i] (LIS length ending at i) and dp_cnt[i] (count of such subsequences).
Longest Bitonic Subsequence: Sequence that first increases then decreases. Combine forward LIS and backward LIS at each position.
Russian Doll Envelopes (LeetCode 354): 2D LIS. Sort by width ascending, then by height descending (for same width). Run LIS on heights only. The descending trick prevents selecting two envelopes of the same width.

What Most Engineers Get Wrong¶

1. Interval DP fill order. You must fill smaller intervals before larger ones. The template loops on length first, then i. If you try to fill row by row (fix i, vary j), you’ll reference dp[k+1][j] entries that haven’t been computed yet. This produces incorrect silent answers.

2. LIS: stopping at O(n²). The O(n²) solution is “good enough” for n ≤ 1000 but fails for n ≤ 100,000. Any serious competitive problem with LIS will have n up to 10^5. If you only know the O(n²) version, you will TLE. Learn patience sorting. The O(n log n) version is also what interviewers at strong companies expect when they ask about LIS.

3. Burst Balloons: thinking about first burst instead of last. Almost every first attempt on Burst Balloons tries to simulate bursting from the outside in. The state space is wrong because the “neighborhood” of each balloon changes with each burst. The only way to get clean, independent subproblems is to define the state around the last balloon to burst in a range. This is counter-intuitive; accept it, internalize it.

Practice Problems¶

(This section is harder than earlier sections. 70% independent solve rate is the honest target.)

Medium¶

Longest Increasing Subsequence — LeetCode 300. Do the O(n²) solution first, then the O(n log n) version. Both matter.
Longest Palindromic Subsequence — LeetCode 516. Interval DP or LCS reduction.
Strange Printer — LeetCode 664. Interval DP. Non-obvious state design.

Hard¶

Burst Balloons — LeetCode 312. The canonical “last operation inversion.” Expect to spend 45–90 minutes here.
Remove Boxes — LeetCode 546. Interval DP with a 3D state. Significantly harder than Burst Balloons. Don’t be discouraged.
Russian Doll Envelopes — LeetCode 354. 2D LIS with the descending trick.
Minimum Cost to Merge Stones — LeetCode 1000. Interval DP with a constraint check (only valid to split when (n-1) % (K-1) == 0).

05 — Interval DP & Subsequence DP¶

Part I — Interval DP¶

The Interval DP Template¶

Problem 1: Matrix Chain Multiplication¶

Problem 2: Burst Balloons¶

Problem 3: Palindrome Partitioning II¶

Part II — Subsequence DP¶

LIS — Longest Increasing Subsequence¶

O(n²) DP Solution¶

O(n log n) Solution — Patience Sorting¶

Longest Palindromic Subsequence¶

LIS Variants Worth Knowing¶

What Most Engineers Get Wrong¶

Practice Problems¶

Medium¶

Hard¶

Navigation¶