Interval DP — Longest Palindromic Subsequence

Interval DP Pattern

States are ranges [i,j]. Fill diagonally: length 1, then 2, then 3, etc. Each interval depends on smaller sub-intervals. Classic "expand from diagonal" pattern.

Recurrence

dp[i][i] = 1 // single char
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])

Interactive Visualization

Computing

Match (diagonal +2)

Source

String:

Step 0 of 0

Range [i,j]

—

Comparing

—

dp[i][j]

—

LPS Length

—

Ready. Press Play or Next to start.

✓ Done

Speed

C++ — LPS

int longestPalindromeSubseq(string s) {
    int n = s.size();
    vector<vector<int>> dp(n, vector<int>(n, 0));
    for (int i = 0; i < n; i++) dp[i][i] = 1;

    for (int len = 2; len <= n; len++) {
        for (int i = 0; i <= n - len; i++) {
            int j = i + len - 1;
            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]);
        }
    }
    return dp[0][n-1];
}

Complexity

Time

O(N²)

Fill upper triangle of N×N table.

Space

O(N²)

2D table. Can reduce to O(N).

📝 Notes

▼