Longest Palindromic Subsequence

Given a non-empty string s consisting of lowercase alphabetic characters, the task is to determine the length of the longest palindromic subsequence (LPS) present in s. A palindromic subsequence is a sequence that reads the same forward and backward, and it is not required to be contiguous within the string.

The solution should implement a dynamic programming approach. The recurrence relation for the dynamic programming solution can be expressed in LaTeX as:

\(dp[i][j] = \begin{cases} 1 & \text{if } i = j,\\[6pt] 2 & \text{if } s[i] = s[j] \text{ and } j = i+1,\\[6pt] dp[i+1][j-1] + 2 & \text{if } s[i] = s[j],\\[6pt] \max(dp[i+1][j], dp[i][j-1]) & \text{if } s[i] \neq s[j].\end{cases}\)

Your program should read from standard input (stdin) and output the result to standard output (stdout).

inputFormat

The input consists of a single line containing the string s composed of lowercase letters.

outputFormat

Output an integer representing the length of the longest palindromic subsequence of the input string.

bbbab

4