Longest Palindromic Subsequence

Given a string s containing only lowercase English letters, find the length of the longest palindromic subsequence in s. A subsequence is a sequence that can be derived from the string by deleting some or no elements without changing the order of the remaining elements.

The problem can be solved using dynamic programming. Let \(dp[i][j]\) denote the length of the longest palindromic subsequence in the substring from index \(i\) to \(j\). The recurrence is given by:

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

Your task is to compute \(dp[0][n-1]\), where \(n\) is the length of s.

inputFormat

The input consists of a single line containing the string s. The string contains only lowercase English letters and has a length between 1 and 1000.

outputFormat

Output a single integer representing the length of the longest palindromic subsequence in s.

## sample

bbbab

4

</p>