O(N^2) DP on intervals and centre expansion

Some problems ask you to compute something for every contiguous subarray or substring. A naive approach checks all pairs of start and end indices, which is O(N^2) pairs. If checking each pair is fast, the total time is acceptable. Dynamic programming over intervals uses this structure.

One common pattern is a recurrence where a larger interval's answer depends on a smaller interval inside it plus a small additional cost. By computing in the right order, you avoid recomputing and build the answer incrementally.

Palindrome checking with centre expansion

A classic example is counting palindromes. One way is to expand from each possible centre: each character (odd-length palindromes) and each pair of adjacent characters (even-length palindromes).

For each centre, expand outward as long as characters match. Record the length of the longest palindrome around that centre. If you expand from all O(N) centres and each expansion takes O(N) time, the total is O(N^2).

1s = "racecar"2
3def expand(s, left, right):4    while left >= 0 and right < len(s) and s[left] == s[right]:5        left -= 16        right += 17    return right - left - 18
9longest = 010for i in range(len(s)):11    # Odd length12    length = expand(s, i, i)13    longest = max(longest, length)14
15    # Even length16    if i < len(s) - 1:17        length = expand(s, i, i + 1)18        longest = max(longest, length)19
20print(f"Longest palindrome in '{s}': length {longest}")

Longest palindrome in 'racecar': length 7

For each odd-length centre (a single character) and each even-length centre (between two characters), you expand left and right. The code records the longest palindrome found. The palindrome ends as soon as characters stop matching.

Centre expansion in code

Expansion from a single centre is simple: start at the centre and move outward while the condition holds. For palindromes, the condition is that the left and right characters match.

1def expand_palindrome(s, left, right):2    """Expand outward from centre; return length of longest palindrome found."""3    while left >= 0 and right < len(s) and s[left] == s[right]:4        left -= 15        right += 16    return right - left - 17
8s = "ababa"9
10# Expand from the middle 'a' at index 211length = expand_palindrome(s, 2, 2)12print(f"From centre at index 2: palindrome length {length}")13
14# Expand from between indices 1 and 2 (even length)15length = expand_palindrome(s, 1, 2)16print(f"From centre between 1 and 2: palindrome length {length}")

From centre at index 2: palindrome length 5
From centre between 1 and 2: palindrome length 0

The function expands outward from a starting position, checking characters at distance d from the centre. It returns how far outward the condition held. For palindromes, it returns the length of the longest palindrome centred there.

Interval DP recurrence

Another way to solve the palindrome problem is with interval DP. Let dp[l][r] be true if the substring from index l to r (inclusive) is a palindrome. Then:

• dp[l][r] is true if arr[l] == arr[r] and dp[l+1][r-1] is true (or l+1 > r-1).

This recurrence builds outward. To compute dp[l][r], you need dp[l+1][r-1], which is a smaller interval. If you compute in order of increasing interval length, all smaller intervals are ready.

1s = "ababa"2n = len(s)3
4dp = [[False] * n for _ in range(n)]5
6# Every single character is a palindrome7for i in range(n):8    dp[i][i] = True9
10# Check pairs and longer11for length in range(2, n + 1):12    for l in range(n - length + 1):13        r = l + length - 114        # A pair, or a longer interval whose inner part is a palindrome15        if s[l] == s[r] and (length == 2 or dp[l + 1][r - 1]):16            dp[l][r] = True17
18# Count palindromes19count = 020for l in range(n):21    for r in range(l, n):22        if dp[l][r]:23            count += 124            print(f"Palindrome: {s[l:r+1]}")25
26print(f"Total: {count}")

Palindrome: a
Palindrome: aba
Palindrome: ababa
Palindrome: b
Palindrome: bab
Palindrome: a
Palindrome: aba
Palindrome: b
Palindrome: a
Total: 9

The outer loop is interval length. The inner loop is the starting position. For each position, you check if the substring is a palindrome by looking at one step inward. This is O(N^2) table entries and O(1) per entry, so O(N^2) total.

Avoiding the full table

With N up to 5000, an O(N^2) table of booleans fits in memory. But some problems need O(N^2) different values at each cell, not just a boolean. An O(N^2) memory table becomes impossible.

You only need the previous "layer": the values from intervals one step smaller. Keep two layers in memory, and overwrite the older one as you compute the new one.

For palindrome problems, you can compute the answer per length in a single pass. You loop over all possible starts, and for each start, you expand outward. You track only the length of the longest palindrome per start, not a full 2D table.

1s = "ababa"2n = len(s)3
4longest = [0] * n5
6for i in range(n):7    # Odd length: expand from i8    left, right = i, i9    while left >= 0 and right < n and s[left] == s[right]:10        longest[i] = max(longest[i], right - left + 1)11        left -= 112        right += 113
14    # Even length: expand from between i and i+115    if i < n - 1:16        left, right = i, i + 117        while left >= 0 and right < n and s[left] == s[right]:18            longest[i] = max(longest[i], right - left + 1)19            left -= 120            right += 121
22print("Longest palindrome from each position:", longest)23print(f"Overall longest: {max(longest)}")

Longest palindrome from each position: [1, 3, 5, 3, 1]
Overall longest: 5

This approach keeps only an array of lengths instead of a full 2D table. You loop over all starting positions and expand from each. Palindromes discovered are recorded in the lengths array.

Why centre expansion is efficient

Centre expansion works because a palindrome grows outward symmetrically. If you know the longest palindrome centred at position i, you can use that information to speed up the search at position i+1. The total number of character comparisons is O(N^2) in the worst case (when the entire string is a palindrome), but the algorithm never repeats work.

Each character is compared at most O(N) times across all expansions. Since there are O(N) centres, the total comparisons are O(N^2). This is optimal for finding all palindromic substrings, because there can be O(N^2) palindromes in a string.

Interval DP makes this explicit: the O(N^2) table has one entry per interval, and filling each entry takes O(1) time (just a comparison and a lookup). The space cost is O(N^2) for the table, but the time is guaranteed O(N^2).

Symmetric sequences beyond palindromes

The same technique applies to other problems. Suppose you need to find the longest symmetric sequence in an array, where symmetric means the values read the same forwards and backwards. The recurrence is almost identical: check if the ends match, then look inside.

Another example is finding the longest alternating subsequence: values that alternate between high and low. The recurrence would be: does arr[l] start an alternation pattern with arr[r]? If so, check arr[l+1] and arr[r-1].

For any problem where the answer for an interval depends on the ends and the smaller interval inside, centre expansion or interval DP applies. The structure is always: compute by increasing interval size, check the boundaries, and recurse inward.

Common mistakes

A common error is using recursion with memoization and forgetting to count all the different (l, r) pairs. If your recurrence visits O(N^2) states and each state takes O(1) or O(log N) time, the total is O(N^2) or O(N^2 log N). But if you forget memoization and recompute the same state many times, it becomes exponential and times out.

Another mistake is building a full O(N^2) table of large values when memory is tight. A 5000×5000 table of 64-bit integers is 200 MB, which fits, but 5000×5000 of Python objects becomes too large. Before you allocate, check how many entries you need and whether you can store only the necessary information.

Also, be careful with the interval boundaries. Some recurrences use inclusive bounds [l, r], others use [l, r). If you mix them, you get off-by-one errors. One line computes arr[l] == arr[r], the next assumes r is exclusive, and the palindrome check breaks.

A fourth error is expanding too far. If you expand from a centre and find no match (characters do not match), you should stop immediately. Continuing to expand past a mismatch wastes time and produces the wrong answer.