Longest Palindromic Subsequence

Logical Breakdown

• [ ] Subproblem Identification:
• [ ] Optimal Substructure:
• [ ] Constraint Handling: (e.g., Modulo \(10^9 + 7\))
• [ ] Optimization: (Matrix Exponentiation if 'A' is huge)

---

Mathematical Rigor

State Definition

Let \(dp[i]\) be the state for the \(i\)-th subproblem.

Recurrence Relation

\[ dp[i] = ... \]

---

Visualization

graph TD A["Current State"] --> B["Previous State 1"] A --> C["Previous State 2"]

---

Complexity Analysis

Approach	Time Complexity	Space Complexity
Iterative DP	\(O(N)\)	\(O(1)\)

---

Code Reference

package com.dsa.dynamic_programming;

import java.util.*;

/ * Problem: Longest Palindromic Subsequence * Group: 11. Dynamic Programming */ / * ============================================================================================ * PROBLEM: Longest Palindromic Subsequence * ============================================================================================ * * --------------------- * 1. Problem Description * --------------------- * Find the length of the longest subsequence in S which is also a palindrome. * * --------------------- * 2. Logical Breakdown * --------------------- * Method 1 (LCS Variation): * The LPS of string S is exactly the LCS of (S, reverse(S)). * * Method 2 (Interval DP): * Let dp[i][j] be the LPS length of substring S[i...j]. * * Recurrence: * 1. If S[i] == S[j]: * Both ends match. They contribute 2 to the length + LPS of the inner part. * dp[i][j] = 2 + dp[i+1][j-1] * * 2. If S[i] != S[j]: * We drop either the left char or the right char. * dp[i][j] = max(dp[i+1][j], dp[i][j-1]) * * Base Cases: * dp[i][i] = 1 (Single char is palindrome of length 1). * * ============================================================================================ */ public class LongestPalindromicSubsequence { public int solve(int A) { // TODO: Implement solution return 0; }

public int solveLPS(String bbbab) {
    return 1;
}

}