The Longest Palindrome You Can Keep
Print the length of the longest SUBSEQUENCE of the string that reads the same forwards and backwards. A subsequence keeps the original order but may delete any characters.
bbbab -> 4 bbbb
character -> 5 carac
The state is the surprise. A single index is not enough, because deciding whether to keep a character requires knowing what is still available at BOTH ends. So the state is a RANGE:
best(i, j) = the longest palindromic subsequence of s[i..j]
and the recursion compares the two ends:
i > j -> 0 empty range
i == j -> 1 single character
s[i] == s[j] -> best(i+1, j-1) + 2
otherwise -> max( best(i+1, j), best(i, j-1) )
When the ends match, taking both is always at least as good as taking either alone, so there is no branch to consider there.
Bottom-up, the order must fill SHORT ranges before long ones, since every
sub-range is strictly shorter. Iterating i downwards and j upwards from i
achieves that, and getting the direction wrong reads uninitialised entries.
There is a one-line alternative: this equals the longest common subsequence of the string and its reverse. That is a correct reduction to problem #237 and worth knowing, though the range recursion is what generalises.