Longest Palindromic Subsequence
Given a string s, find the longest palindromic subsequence's length in s.
A subsequence is a sequence that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements.
Examples
Input: "bbbab"
Output: 4
Input: "cbbd"
Output: 2
Hints
Consider using a 2D DP table where `dp[i][j]` represents the length of the longest palindromic subsequence in the substring `s[i..j]`.
The base case is when `i == j`, where `dp[i][j] = 1` since a single character is always a palindrome of length 1.
For the recursive case, if `s[i] == s[j]`, then `dp[i][j] = dp[i+1][j-1] + 2`; otherwise, `dp[i][j] = max(dp[i+1][j], dp[i][j-1])`. Fill the table diagonally to ensure dependencies are resolved.
Longest Palindromic Subsequence
Given a string `s`, find the longest palindromic **subsequence**'s length in `s`.