Palindrome DP

Overview

Palindrome problems need a different table shape: the state is an interval [i..j] rather than a prefix. dp[i][j] answers the question for the substring from i to j, and the recurrence looks inward — if the two ends match, the answer extends the result for [i+1..j-1]. That inward dependency forces a specific fill order: by increasing interval length, so every shorter interval is already solved when a longer one needs it. Getting that order wrong is the defining mistake of interval DP.

Why it matters

Interval DP covers a family well beyond palindromes: matrix-chain multiplication, optimal binary search trees, burst-balloons-style problems, and parsing with context-free grammars (CYK) all use the same "solve short ranges first" structure. Palindromes are the gentlest introduction because the recurrence is short and the answer is easy to verify by eye.

Core concepts

Interval state. dp[i][j] covers s[i..j] inclusive. The diagonal dp[i][i] is the base case — a single character is a palindrome of length 1.

Longest palindromic subsequence. If s[i] == s[j], the two ends pair up: dp[i][j] = dp[i+1][j-1] + 2. Otherwise drop one end: max(dp[i+1][j], dp[i][j-1]).

Fill by increasing length. dp[i][j] needs dp[i+1][j-1], a shorter interval. Loop over length from 2 upward (or iterate i downward and j upward) so dependencies are always ready. Filling in plain row-major order reads uninitialised cells.

Subsequence vs substring. Longest palindromic subsequence allows gaps and uses the recurrence above; longest palindromic substring requires contiguity and either resets on mismatch or uses the expand-around-centre technique in O(1) space.

The two-character case. dp[i][i+1] is 2 when the characters match, else 1. With the length-based loop this falls out naturally, but it is worth checking explicitly because dp[i+1][j-1] refers to an empty interval there.

Complexity. O(n^2) time and O(n^2) space; the space can be reduced but the table is usually kept for reconstruction.

Syntax notes

#include <stdlib.h>
#include <string.h>

/* longest palindromic subsequence */
int lps(const char *s) {
    int n = (int)strlen(s);
    if (n == 0) return 0;
    int *dp = calloc((size_t)n * n, sizeof *dp);
    if (!dp) return -1;
    for (int i = 0; i < n; i++) dp[i*n + i] = 1;          /* base: single char */
    for (int len = 2; len <= n; len++)                    /* SHORT intervals first */
        for (int i = 0; i + len - 1 < n; i++) {
            int j = i + len - 1;
            if (s[i] == s[j])
                dp[i*n + j] = (len == 2) ? 2 : dp[(i+1)*n + (j-1)] + 2;
            else {
                int a = dp[(i+1)*n + j], b = dp[i*n + (j-1)];
                dp[i*n + j] = (a > b) ? a : b;
            }
        }
    int r = dp[0*n + (n-1)];
    free(dp);
    return r;
}

Key points:

• The outer loop is over length, not over i — that is what satisfies the inward dependency.
• len == 2 is handled explicitly because dp[i+1][j-1] would be an empty interval.
• The answer is dp[0][n-1], the full-string interval.

Lesson

The longest palindromic subsequence and the minimum insertions to form a palindrome are solved by interval DP: dp[i][j] over the substring from i to j, filled by increasing length so inner intervals are ready before outer ones. Min insertions is simply length minus the LPS.

Code examples

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
static int lps(const char*s){int n=strlen(s);if(!n)return 0;int*dp=calloc((size_t)n*n,sizeof(int));for(int i=0;i<n;i++)dp[i*n+i]=1;for(int len=2;len<=n;len++)for(int i=0;i+len-1<n;i++){int j=i+len-1;if(s[i]==s[j])dp[i*n+j]=(len==2?2:dp[(i+1)*n+j-1]+2);else{int a=dp[(i+1)*n+j],b=dp[i*n+j-1];dp[i*n+j]=a>b?a:b;}}int r=dp[n-1];free(dp);return r;}
int main(void){
    const char *s="character";
    int L=lps(s);
    printf("longest palindromic subsequence of \"%s\" = %d\n", s, L);
    printf("min insertions to make it a palindrome = %d\n", (int)strlen(s)-L);
    return 0;
}

Line by line

Common mistakes

Filling the table in the wrong order (outer ranges before inner ones).

Debugging tips

Compiler errors and warnings:

• -Wsign-compare from strlen; cast to int once.
• No warning for the wrong fill order — it silently reads zeros.

Runtime symptoms:

• Answers are too small or plainly wrong. You filled row-major instead of by increasing length, so dp[i+1][j-1] was still 0 when used. This is the signature interval-DP bug.
• Crash or garbage at length 2. dp[i+1][j-1] with j = i+1 refers to an empty interval; special-case len == 2.
• Returns the string length for any input. You wrote longest common subsequence against the reversed string but indexed it wrongly, or the match branch always fires — check the comparison.
• Substring expected, subsequence delivered. These are different problems; contiguity requires a different recurrence.
• Empty string crashes. Guard n == 0 before allocating n*n.

Technique: print the upper triangle of the table for a 5-character string. Interval DP fills diagonally outward, and a wrong order is visible immediately as zeros where numbers should be.

Memory safety

• n * n overflow. For a long string this multiplication can overflow int; compute in size_t and bound the input length before allocating.
• Guard the empty string. calloc(0) and then indexing dp[0*n + (n-1)] with n = 0 reads out of bounds. Return early.
• Only the upper triangle is meaningful. Entries with i > j are never written; reading them yields the calloc zeros, which is safe but meaningless — do not treat them as answers.
• Zero-initialisation is required because the recurrence reads shorter intervals that may not have been explicitly set for the empty case.
• Index arithmetic. Every access is dp[i*n + j]; using a stride other than n silently reads the wrong cell.
• Free on all paths.

Real-world uses

Concrete uses: Interval DP is the engine behind matrix-chain multiplication ordering, optimal binary search tree construction, and CYK parsing for context-free grammars. Palindrome detection specifically appears in bioinformatics (reverse-complement palindromes mark restriction sites) and in text-processing puzzles. The "solve short ranges first" structure generalises to any problem where combining two adjacent solved ranges produces a larger one.

Professional best practices:

Beginner:

• Always loop over interval length in the outer loop.
• Verify with a short string you can check by hand.

Intermediate:

• Be explicit about subsequence versus substring in naming and documentation; they are routinely confused.
• For longest palindromic substring, expand-around-centre is O(n^2) time but O(1) space and much simpler than a table.
• Keep the table when you need to output the palindrome itself; the score alone does not identify it.

Practice tasks

1. (Beginner) Longest palindromic subsequence. Implement int lps(const char *s). Example: "bbbab" -> 4; "cbbd" -> 2. Concepts: interval state, fill by length.

2. (Beginner) Is it a palindrome? Write a simple two-pointer int is_pal(const char *s) and use it to spot-check your DP on inputs that are entirely palindromic. Concepts: validating a DP against a simple oracle.

3. (Intermediate) Longest palindromic substring. Implement the contiguous version with expand-around-centre and compare its answer with the subsequence version. Example: "babad" -> "bab" (length 3) vs subsequence 3. Concepts: substring vs subsequence.

4. (Intermediate) Reconstruct the palindrome. Output the actual longest palindromic subsequence, not just its length. Hint: walk the table from [0][n-1], moving inward on matches. Concepts: DP reconstruction.

Summary

Palindrome DP uses an interval state — dp[i][j] for the substring s[i..j] — with the diagonal seeded to 1. Matching ends add 2 to the inner interval; differing ends take the better of dropping one end. Because the recurrence looks inward at a shorter interval, the table must be filled by increasing length, and filling row-major instead is the classic silent failure. Handle len == 2 explicitly since the inner interval is empty there, guard the empty string before allocating n*n, and keep in mind that subsequence and substring are genuinely different problems.

Practice with these exercises

• Longest palindromic subsequence
• Min insertions for a palindrome