Introduction

A palindrome is a sequence that reads the same backward as forward. In computational terms, the Longest Palindromic Subsequence (LPS) problem involves finding the longest subsequence within a string that is a palindrome. Unlike substrings, subsequences are not required to have consecutive characters. The LPS problem is a classic question in dynamic programming (DP), offering a beautiful display of optimal substructure and overlapping subproblems characteristics.

Dynamic Programming Approach

The dynamic programming approach to solving the LPS problem involves constructing a table to store results of subproblems, which helps avoid redundant computations.

Problem Formulation

Given a string $s$ of length $n$``, define L[i][j] as the length of the longest palindromic subsequence in the substring ``$s[i...j]$. The goal is to compute L[0][n-1].

Transition Formula

To fill the DP table, use the following rules:

1. Base Case: When dealing with a single character, i.e., i == j, a single character is itself a palindrome of length 1. Thus:
   $$L[i][i] = 1$$
2. Recurrence Relation: For longer sequences, if the boundary characters match (i.e., s[i] == s[j]), then they contribute to the LPS, and you can extend the solution for the inner substring:
   $$L[i][j] = L[i+1][j-1] + 2$$
   If the boundary characters do not match:
   $$L[i][j] = \max(L[i+1][j], L[i][j-1])$$

Algorithm

1. Initialize a DP table L of size $n \times n$.
2. Set all diagonal elements L[i][i] to 1, representing base cases of single-character palindromes.
3. For each substring length cl from 2 to n, compute LPS values using the transition formulas.
4. Populate L iteratively, with L[0][n-1] eventually containing the length of the LPS for the entire string.

• Time Complexity: The solution consists of a double loop, resulting in a time complexity of $O(n^2)$.
• Space Complexity: Requires an $n \times n$ table to store intermediate results, so the space complexity is also $O(n^2)$.
• Space Optimization: The full table is often not required simultaneously. Space can be reduced to $O(n)$ by maintaining only two rows of the DP table at any time.
• Reconstructing the LPS: For more insight, reconstruct the palindrome itself by backtracking through the table based on chosen paths.