DP on Intervals: Dynamic Programming Deep Dive

1. Introduction and Core Concepts

DP on intervals, often called interval dynamic programming or range DP, is a specialized paradigm within dynamic programming where the state is defined by the boundaries of a contiguous interval or subarray. Unlike linear DP where the state typically depends on a single prefix index dp[i], interval DP defines dp[i][j] as the optimal solution for the subarray from index i to index j inclusive. This approach is indispensable when the solution to a problem cannot be built by simply appending one element at a time, but instead requires considering how to optimally split, merge, or partition an interval into smaller subintervals.

The core intuition behind dp on intervals is that the optimal solution for a large interval is composed of optimal solutions for its smaller subintervals. The problem exhibits optimal substructure over intervals: to solve [i, j], we try every possible partition point k where i <= k < j, combine the results of [i, k] and [k+1, j], and add the cost of merging them. This makes it fundamentally different from knapsack or LIS-style DP, where decisions are sequential. Interval DP is inherently two-dimensional and is filled diagonally by increasing interval length, not row by row.

Why does this matter? Many classic optimization problems have an interval structure that linear DP cannot capture. Consider matrix chain multiplication: the cost of multiplying matrices from i to j depends on where you place the final parenthesization, which splits the chain into two independent subchains. Similarly, finding the minimum cost to merge stones, the optimal way to triangulate a polygon, or the best way to burst balloons all require reasoning about intervals. Without interval DP, these problems would require exponential brute force. With it, they become solvable in polynomial time, typically O(n^3), which is a dramatic improvement for moderate input sizes.

When to Recognize an Interval DP Problem

You should suspect dp on intervals when the problem statement involves a sequence, array, or string and asks for an optimal way to partition, merge, or parenthesize it. Key phrases include "minimum cost to merge," "optimal way to cut," "maximum score by removing elements," or "number of ways to triangulate." Another strong signal is that the order of elements matters and the operation on an interval affects its neighbors after merging, as seen in the Burst Balloons problem.

A second signal is the failure of greedy or linear DP. If considering elements from left to right forces you to look ahead arbitrarily far, or if the cost of a decision depends on the entire current interval rather than just a prefix, interval DP is likely the right tool. The state must capture both endpoints because the interior cannot be summarized by a single value. This two-boundary state is the hallmark of the technique and the reason it is more powerful than one-dimensional DP for this class of problems.

2. How It Works

The mechanism of interval DP rests on three pillars: state definition, recurrence relation, and filling order. The state dp[i][j] is almost always defined as the optimal value (minimum cost, maximum score, boolean feasibility, or count) for the subproblem restricted to the interval [i, j]. For problems on strings of length n, this creates an n x n table. The answer to the original problem is typically dp[0][n-1], representing the entire array. Some variants use dp[i][j] to represent an interval open on one side or with an extra dimension, but the two-index core remains.

The recurrence relation is where the interval splitting happens. For most problems, the transition iterates over a split point k:

dp[i][j] = min/max over k in [i, j-1] of ( dp[i][k] + dp[k+1][j] + cost(i, j, k) )

Here, cost(i, j, k) is the problem-specific price of combining the two subintervals. In matrix chain multiplication, it is dims[i-1] * dims[k] * dims[j]. In optimal binary search tree, it is the sum of frequencies in [i, j]. In other problems like Strange Printer or Minimum Cost to Cut a Stick, the recurrence may look slightly different, such as dp[i][j] = dp[i][k] + dp[k+1][j] - overlap or considering the last operation performed inside the interval. The unifying theme is that the larger interval is built from two smaller, disjoint intervals that partition it.

The filling order is critical and is a common source of bugs. Since dp[i][j] depends on strictly smaller intervals [i, k] and [k+1, j], we must ensure those values are already computed. This is achieved by iterating by interval length (also called gap strategy). We first fill all intervals of length 1 (the diagonal), then length 2, then length 3, up to length n. An alternative is to iterate i from n-1 down to 0 and j from i+1 to n-1, which also guarantees dependencies are resolved. Top-down memoization with recursion naturally handles this order via the call stack, but bottom-up is often more efficient and avoids recursion depth limits.

Base Cases and Initialization

Base cases for interval DP are intervals of length 1 or 2. For length 1, dp[i][i] is usually 0 (no cost to handle a single element), 1 (one palindrome of length 1), or the value of the single element itself, depending on whether we are minimizing cost, counting, or maximizing score. For length 2, the solution can often be computed directly without a split. Proper initialization is essential: for minimization problems, initialize dp[i][j] to infinity before taking the minimum over k; for maximization, initialize to negative infinity. Empty intervals dp[i][i-1] are sometimes defined as 0 to simplify recurrences that include edge splits.

Another nuance is whether the DP table should be n x n or (n+1) x (n+1). When the interval is defined as [i, j) (half-open) or when we pad the array with sentinels (as in Burst Balloons where we add 1 at both ends), an (n+2) x (n+2) table is cleaner. The choice affects index arithmetic but not the asymptotic complexity. Consistency in interval definition throughout the implementation is more important than which convention is chosen.

3. Implementation

Implementing dp on intervals can be done top-down with memoization or bottom-up with nested loops. Bottom-up is generally preferred in Python for performance and to avoid recursion limits on large n, but top-down can be more intuitive for complex recurrences. Below is the canonical bottom-up template that applies to the vast majority of interval DP problems.

# Generic Interval DP Template - Bottom-Up Gap Strategy
def interval_dp_template(arr):
    n = len(arr)
    # dp[i][j] = optimal value for interval [i, j] inclusive
    dp = [[0] * n for _ in range(n)]

    # Base case: intervals of length 1
    for i in range(n):
        dp[i][i] = 0  # or 1, or arr[i] depending on problem

    # Fill by increasing interval length (gap)
    for length in range(2, n + 1):  # length = 2 .. n
        for i in range(n - length + 1):
            j = i + length - 1
            dp[i][j] = float('inf')  # for minimization
            # Try every partition point k between i and j-1
            for k in range(i, j):
                # Recurrence: combine left and right + merge cost
                cost = dp[i][k] + dp[k+1][j] + merge_cost(arr, i, j, k)
                if cost < dp[i][j]:
                    dp[i][j] = cost
    return dp[0][n-1] if n > 0 else 0

def merge_cost(arr, i, j, k):
    # Problem-specific: e.g., sum(arr[i:j+1]) or dims[i]*dims[k+1]*dims[j+1]
    return 0

This template runs in O(n^3) time and O(n^2) space. The outer two loops enumerate O(n^2) intervals, and the inner loop tries O(n) split points. For many problems, this is optimal. The merge_cost function is where problem logic is injected and should be O(1) if possible, often using prefix sums to compute interval sums quickly.

Next, we look at a classic concrete implementation: Matrix Chain Multiplication. Given dimensions p where matrix Ai has dimensions p[i-1] x p[i], find the minimum number of scalar multiplications needed to multiply the chain.

def matrix_chain_order(p):
    """
    p: list of dimensions, len(p) = n+1 for n matrices
    Returns minimum multiplication cost
    """
    n = len(p) - 1  # number of matrices
    # dp[i][j] = min cost to multiply matrices i..j (1-indexed for clarity)
    # We use 0-indexed dp of size n x n, where dp[i][j] corresponds to Ai..Aj
    dp = [[0] * n for _ in range(n)]

    # length = chain length
    for length in range(2, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            dp[i][j] = float('inf')
            for k in range(i, j):
                # Cost = cost of left + cost of right + cost to multiply results
                # Left result is p[i] x p[k+1], right is p[k+1] x p[j+1]
                q = dp[i][k] + dp[k+1][j] + p[i] * p[k+1] * p[j+1]
                if q < dp[i][j]:
                    dp[i][j] = q
    return dp[0][n-1]

# Example
p = [10, 30, 5, 60]  # A1:10x30, A2:30x5, A3:5x60
print(matrix_chain_order(p))  # Output: 4500  ((A1*A2)*A3 is optimal)

The third example demonstrates a more subtle interval DP where the recurrence is not a simple split. In Burst Balloons, bursting a balloon gives coins based on its neighbors, which change as balloons are burst. The trick is to think in reverse: consider which balloon is burst *last* in interval [i, j].

def max_coins(nums):
    """
    Burst Balloons - Interval DP with reverse thinking
    nums: list of balloon values
    """
    # Add sentinels: 1 at both ends to handle boundaries
    vals = [1] + nums + [1]
    n = len(vals)
    dp = [[0] * n for _ in range(n)]

    # length = interval length, at least 3 because we need i < k < j
    for length in range(2, n):  # length 2 means no balloon inside, cost 0
        for left in range(n - length):
            right = left + length
            # Try every balloon k as the LAST to burst in (left, right)
            for k in range(left + 1, right):
                # Coins from bursting k last: vals[left]*vals[k]*vals[right]
                # plus optimal solutions for left part and right part
                coins = vals[left] * vals[k] * vals[right] + dp[left][k] + dp[k][right]
                if coins > dp[left][right]:
                    dp[left][right] = coins
    return dp[0][n-1]

# Example
print(max_coins([3, 1, 5, 8]))  # Output: 167

Finally, an example of interval DP for string problems: Minimum Palindromic Partition Cuts. While it can be solved with linear DP after precomputing palindromes, the pure interval version illustrates the pattern for counting and optimization on strings.

def min_palindrome_cuts(s):
    """
    Minimum cuts to partition s into palindromic substrings
    Uses interval DP to precompute palindromes + DP for cuts
    """
    n = len(s)
    if n == 0:
        return 0

    # is_pal[i][j] = True if s[i:j+1] is palindrome
    is_pal = [[False] * n for _ in range(n)]
    for i in range(n):
        is_pal[i][i] = True
    for length in range(2, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            if s[i] == s[j]:
                if length == 2 or is_pal[i+1][j-1]:
                    is_pal[i][j] = True

    # dp[i][j] = min cuts for s[i:j+1]
    dp = [[0] * n for _ in range(n)]
    for length in range(2, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            if is_pal[i][j]:
                dp[i][j] = 0
            else:
                dp[i][j] = float('inf')
                for k in range(i, j):
                    # cut between k and k+1
                    cuts = dp[i][k] + dp[k+1][j] + 1
                    if cuts < dp[i][j]:
                        dp[i][j] = cuts
    return dp[0][n-1]

print(min_palindrome_cuts("aab"))  # Output: 1  ("aa" | "b")
print(min_palindrome_cuts("abccbc"))  # Output: 2

4. Step-by-Step Example

Let us walk through Matrix Chain Multiplication in detail to see how the DP table is filled. Consider matrices A1: 10x30, A2: 30x5, A3: 5x60 with dimension array p = [10, 30, 5, 60]. We have n=3 matrices, so our DP table is 3x3. We initialize dp[i][i] = 0 for all i, since a single matrix requires no multiplication.

We begin with intervals of length 2. For [0,1] (matrices A1*A2): there is only one split k=0, cost = dp[0][0] + dp[1][1] + p[0]*p[1]*p[2] = 0 + 0 + 10*30*5 = 1500. So dp[0][1] = 1500. For [1,2] (A2*A3): split k=1, cost = 0 + 0 + 30*5*60 = 9000. So dp[1][2] = 9000. At this point the table has its first off-diagonal filled.

Now we handle length 3, the full interval [0,2] (A1*A2*A3). We try two possible split points. Split at k=0: (A1)*(A2*A3) cost = dp[0][0] + dp[1][2] + p[0]*p[1]*p[3] = 0 + 9000 + 10*30*60 = 9000 + 18000 = 27000. Split at k=1: (A1*A2)*(A3) cost = dp[0][1] + dp[2][2] + p[0]*p[2]*p[3] = 1500 + 0 + 10*5*60 = 1500 + 3000 = 4500. Taking the minimum, dp[0][2] = 4500, which corresponds to parenthesization (A1*A2)*A3. The answer is dp[0][2].

Visualizing the Fill Order

The fill order can be visualized as filling the DP table diagonal by diagonal. The main diagonal (length 1) is zero. The next diagonal (length 2) contains dp[0][1] and dp[1][2]. The final cell dp[0][2] depends on both of those diagonals, which is why it is computed last. If we attempted to compute dp[0][2] before dp[1][2], we would use an uninitialized value and get an incorrect result. This dependency structure is why nested loops must be ordered by length, not by i then j naively.

This same walkthrough pattern applies to all interval DP problems. For Burst Balloons with [3,1,5,8], the padded array is [1,3,1,5,8,1]. Length 2 intervals like [0,2] (values 1,3,1) have one choice k=1 giving 1*3*1=3. As length grows, each interval tries every k as the last burst, combining left and right optimal scores. The final answer dp[0][5]=167 emerges from the optimal split sequence, which can be reconstructed by storing the k that gave the optimum at each cell.

5. Complexity Analysis

The complexity of dp on intervals is dominated by the three nested loops: two for enumerating intervals and one for trying split points. For an input of size n, there are O(n^2) intervals and O(n) choices per interval, leading to O(n^3) time in the general case. Space is O(n^2) for the DP table. This holds for the classic problems like matrix chain multiplication, optimal binary search tree, and burst balloons without optimization. The constant factors are moderate, but O(n^3) becomes prohibitive beyond n ~ 500 in Python.

Best, average, and worst cases are often identical for the naive implementation because the loops run the same number of iterations regardless of input values. The only variation comes from early pruning or problem-specific costs that might allow skipping some k values, but asymptotically the complexity remains cubic. Space is always quadratic because the entire table is needed to answer queries for larger intervals, though some optimizations can reduce it in special cases.

Optimizations can dramatically improve these bounds. Knuth optimization applies when the quadrangle inequality holds and the optimal split point is monotonic, reducing time to O(n^2). The divide and conquer optimization (Knuth-Yao) and the use of prefix sums to make cost(i,j,k) O(1) are also common. For problems where the cost function is arbitrary, no optimization may be possible and O(n^3) is the lower bound.

When analyzing a specific problem, pay attention to the cost of computing cost(i,j,k). If it requires summing an interval naively in O(n), the total time becomes O(n^4). Precomputing prefix sums to answer interval sums in O(1) is therefore not just an optimization but a necessity to achieve the advertised O(n^3) bound. Similarly, for string problems where palindrome checks are needed, precomputing an is_pal table in O(n^2) avoids an extra O(n) factor inside the main loops.

6. Variations and Optimizations

Several powerful optimizations exist for interval DP, each applicable under specific conditions. The most famous is Knuth optimization, which reduces O(n^3) to O(n^2) when the DP satisfies quadrangle inequality and monotonicity of the optimal split point. Formally, if opt[i][j] is the smallest k achieving the optimum for dp[i][j], and opt[i][j-1] <= opt[i][j] <= opt[i+1][j], then when computing dp[i][j] we only need to try k in that narrowed range. This applies to optimal binary search tree and the optimal matrix chain with certain cost functions, but not to burst balloons.

Another optimization is the use of prefix sums and difference arrays to make merge costs O(1). In the "Minimum Cost to Merge Stones" problem where the cost to merge stones from i to j is the sum of that interval, a naive sum would be O(n) per transition. Precomputing prefix[0]=0, prefix[i+1]=prefix[i]+stones[i] allows sum(i,j)=prefix[j+1]-prefix[i] in constant time. This is a small implementation detail with large performance impact, often the difference between TLE and AC in competitive programming.

A third variation is changing the interval definition itself. Some problems require a 3D DP where dp[i][j][k] adds a dimension for the number of partitions or merges, as in "Merge Stones with K piles" where you can only merge exactly K piles at a time. The recurrence then becomes dp[i][j][p] = min(dp[i][k][p-1] + dp[k+1][j][1]). Another variation is the "gap DP" for strings where dp[i][j] depends on dp[i+1][j-1] rather than a split, as in longest palindromic subsequence, which still follows the interval filling order but has O(n^2) time because there is no inner k loop.

Memoization vs Tabulation Trade-offs

Top-down memoization is often easier to write for complex recurrences, especially when not all intervals are needed. For example, in Strange Printer where dp[i][j] can be derived from dp[i][j-1] if s[j]==s[k], many states are pruned and memoization may visit far fewer than O(n^2) states. However, recursion overhead and Python recursion limits can be problematic for n > 1000. Bottom-up tabulation guarantees all states are computed, uses iterative loops that are faster in Python, and makes it easier to apply Knuth optimization because the opt table is filled in order.

Space optimization is rarely possible for general interval DP because future intervals depend on many smaller intervals scattered across the table. Unlike linear DP where only the previous row is needed, interval DP needs random access to any subinterval. The exception is when the recurrence only depends on intervals of length len-1 or len-2, as in some palindrome problems, where two rows suffice. For most optimization problems, the full O(n^2) table must be retained.

7. Real-World Applications

While interval DP is often taught through abstract puzzles, its principles power real systems in web infrastructure, databases, and networks. In database query optimization, the query planner must find the optimal join order for tables T1 JOIN T2 JOIN ... JOIN Tn. The cost of joining two intermediate results depends on their sizes and available indexes, exactly analogous to matrix chain multiplication where dimensions correspond to table cardinalities. Modern databases like PostgreSQL use DP over subsets (a close cousin of interval DP when join graphs are linear) to find the cheapest join order, directly impacting query latency for web applications.

In compilers and web servers, optimal code generation and request batching benefit from interval reasoning. A compiler may need to optimally parenthesize expression trees or merge intermediate code blocks to minimize register spills. A web server handling HTTP/2 stream multiplexing or batching database writes may need to partition a sequence of requests into optimally sized batches where the cost of processing a batch is non-linear. The "minimum cost to cut a stick" problem maps directly to optimal placement of cache invalidation points in a CDN: cutting a cached asset into chunks has a cost proportional to chunk size, and the order of cuts affects total work.

In bioinformatics and natural language processing, interval DP is foundational. RNA secondary structure prediction finds the maximum number of base pairs in an RNA sequence where pairs cannot cross, which is precisely an interval DP: dp[i][j] = max(dp[i+1][j], max over k where i pairs with k of dp[i+1][k-1] + 1 + dp[k+1][j]). In NLP, the CKY algorithm for parsing context-free grammars uses interval DP to determine if a sentence can be derived from a grammar, with dp[i][j][A] indicating whether substring [i,j] can be derived from non-terminal A. These algorithms run on large-scale data pipelines that feed search engines and recommendation systems.

Even in front-end development, interval DP appears in disguised form. The classic "word wrap" or text justification problem, where a paragraph must be broken into lines to minimize raggedness, is an interval DP where dp[i] depends on all j > i where words i..j fit on one line. While this is technically linear DP, the cost function involves an interval and the optimal solution requires considering all possible line breaks, sharing the same split-enumeration mindset. Understanding interval DP thus builds intuition for a wide class of partitioning problems encountered in full-stack engineering.

8. Comparison with Alternatives

Interval DP is not the only way to solve partitioning problems, and choosing the right technique depends on problem structure. Linear DP works when the decision at position i only depends on a prefix up to i-1, such as in longest increasing subsequence or 0/1 knapsack. Divide and conquer works when subproblems are independent and do not overlap, allowing recursion without memoization. Interval DP sits between them: subproblems overlap heavily (hence memoization helps) but the state requires two boundaries because the cost of an interval cannot be summarized by a single prefix value.

Compared to brute force recursion that tries all binary tree structures (Catalan number many, exponential), interval DP reduces the complexity to polynomial by reusing overlapping subproblems. Compared to greedy algorithms that might try to always merge the smallest intervals first (as in Huffman coding), interval DP is necessary when greedy fails due to non-local costs. For example, merging stones with arbitrary costs is not solved by Huffman; the order matters and requires DP.

Another alternative is DP over subsets (bitmask DP), which is used when the interval is not contiguous or the order does not matter, such as in traveling salesman or optimal join order for non-linear join graphs. Subset DP is O(3^n) or O(n^2 * 2^n) and is far more expensive than interval DP's O(n^3), but it handles arbitrary subsets. If the problem has a linear order and the cost of a subset depends only on its interval, interval DP is exponentially faster and should be preferred.

The key takeaway is to analyze the dependency structure. If your recurrence needs both i and j to describe the remaining subproblem, linear DP is insufficient. If the cost of combining intervals depends on the entire interval (e.g., sum or product of its elements), interval DP is likely required. If the problem can be split into independent halves with no cross-cost, divide and conquer may be simpler and faster.

9. Common Mistakes and Best Practices

One of the most frequent mistakes is incorrect loop order. Beginners often write loops as for i in range(n): for j in range(i, n): and then try to compute dp[i][j] from dp[i][k] and dp[k+1][j] before those values are ready. The correct order is by increasing length, ensuring all smaller intervals are computed first. Always structure loops as for length in range(...): for i in range(...): j = i+length-1. A quick sanity check is to verify that any dp access inside the inner loop has interval length strictly smaller than the current length.

Another common pitfall is off-by-one errors and sentinel handling. In burst balloons, forgetting to pad with 1s leads to complex boundary checks. In matrix chain, mixing 0-indexed and 1-indexed dimensions causes wrong costs. Define clearly whether dp[i][j] is inclusive or exclusive and whether p has length n or n+1, and stick to it. Using half-open intervals [i, j) can sometimes simplify code because length = j - i and empty intervals are naturally i==j, but it requires adjusting all recurrences.

A third mistake is not precomputing interval costs efficiently. Computing sum(arr[i:j+1]) inside the innermost k loop turns O(n^3) into O(n^4) and will time out. Always precompute prefix sums for sums, and precompute palindrome tables for string problems. Similarly, for minimization problems, failing to initialize dp[i][j] to infinity before the k loop results in taking the minimum with a stale zero value. For maximization, initialize to -inf or 0 if costs are non-negative, but be explicit.

Best Practices for Clean Implementation

Use descriptive variable names: left, right, mid or i, j, k consistently, and name the DP table meaningfully. Add comments stating the invariant: # dp[i][j] = min cost to ... for interval [i,j]. This prevents confusion when revisiting code. When reconstructing the solution (e.g., the actual parenthesization), maintain a parallel choice[i][j] table that stores the k achieving the optimum, then write a recursive reconstruction function.

Test on small cases manually. For n=1, n=2, and n=3, you can brute force all possibilities and compare against DP output. Write a brute force recursive function without memoization for n <= 8 and use it as a verifier in unit tests. Also test edge cases: empty array, all equal values, and strictly increasing dimensions. Finally, consider Python recursion limits and performance: for n > 400, O(n^3) in pure Python may be too slow; consider PyPy, Numba, or optimizing inner loops with local variable binding.

Lastly, document the recurrence before coding. Writing the mathematical recurrence on paper first, including base cases and the range of k, catches logical errors early. For example, for strange printer: dp[i][j] = dp[i][j-1] + 1 if s[j] != s[k] else min(dp[i][j], dp[i][k] + dp[k+1][j-1]). Translating this directly to code is far less error-prone than inventing the recurrence while coding.

10. Interview Questions

Interval DP is a favorite in technical interviews for senior and algorithmic roles because it tests ability to define non-trivial states and handle two-dimensional dependencies. Interviewers expect you to recognize the interval pattern, derive the recurrence, analyze complexity, and code the gap loop correctly. Below are common questions with guidance on what interviewers look for.

Question 1: Minimum Cost to Merge Stones

Given n piles of stones with sizes stones[i], you can merge K consecutive piles into one pile with cost equal to the sum of those piles. Find the minimum cost to merge all piles into one, or -1 if impossible. This is a classic interval DP with an extra dimension. The interviewer wants to see if you handle the feasibility condition (n-1) % (K-1) == 0 and define dp[i][j][p] or use a 2D DP where dp[i][j] is the min cost to merge [i,j] into as few piles as possible. The recurrence splits at k stepping by K-1 and adds sum(i,j) only when the interval can be fully merged. Discuss prefix sums and O(n^3) time.

Question 2: Burst Balloons

Given n balloons with values nums[i], bursting balloon i gives nums[left] * nums[i] * nums[right] coins where left and right are adjacent balloons after bursting. Find maximum coins. The key insight is reverse thinking: consider the last balloon burst in interval (left, right). Many candidates try forward DP and fail because neighbors change. The optimal solution uses padded array and dp[left][right] = max(dp[left][k] + dp[k][right] + vals[left]*vals[k]*vals[right]). Interviewers check if you can explain why forward DP does not work and why the last-burst formulation creates independent subproblems.

Question 3: Strange Printer

A printer prints the same character over any interval in one turn. Find minimum turns to print string s. The recurrence is dp[i][j] = dp[i][j-1] + 1 initially, then for any k in [i, j-1] where s[k]==s[j], dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j-1]). This tests handling of non-split recurrences and overlapping subproblems where equality allows saving a turn. The interviewer will probe your understanding of why s[k]==s[j] allows merging prints and how the interval DP still fills by length.

Question 4: Longest Palindromic Subsequence and Palindromic Partitioning

Find the longest palindromic subsequence or minimum cuts to partition into palindromes. For LPS, the recurrence is 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]), which is O(n^2) without a k loop, illustrating a gap DP variant. For partitioning, you need to precompute palindromes. Interviewers use this to test if you can distinguish O(n^3) split-based interval DP from O(n^2) gap DP and explain the difference in dependencies.

Question 5: Optimal Binary Search Tree

Given sorted keys and their search frequencies, build a BST minimizing expected search cost. This is the textbook Knuth optimization problem. The naive O(n^3) solution is dp[i][j] = min_k(dp[i][k-1] + dp[k+1][j]) + sum(freq[i..j]). The follow-up is to optimize to O(n^2) using Knuth's monotonicity. Strong candidates will mention the quadrangle inequality condition and show how to restrict k to [opt[i][j-1], opt[i+1][j]]. This question separates those who memorize templates from those who understand optimization conditions.

To prepare, practice coding the gap loops without reference, explaining the state definition aloud, and analyzing time and space. Interviewers value clear communication of why interval DP is needed over linear DP, and the ability to derive the recurrence from first principles rather than recalling it verbatim.