Dada uma sequência, encontre o comprimento da subsequência palíndrômica mais longa nela.
 

Como outro exemplo, se a sequência fornecida for “BBABCBCAB”, a saída deve ser 7, pois “BABCBAB” é a subsequência palíndrômica mais longa nela. “BBBBB” e “BBCBB” também são subsequências palindrômicas da sequência dada, mas não as mais longas. 

1)
Subestrutura ótima:  Seja X [0..n-1] a sequência de entrada de comprimento ne L (0, n-1) o comprimento da subseqüência palíndrômica mais longa de X [0..n-1]. 
Se o último e o primeiro caracteres de X forem iguais, então L (0, n-1) = L (1, n-2) + 2. Caso 
contrário, L (0, n-1) = MAX (L (1, n-1 ), L (0, n-2)). 
A seguir está uma solução recursiva geral com todos os casos tratados. 

Solução de Programação Dinâmica  

<?php
// A Dynamic Programming based
// PHP program for LPS problem
// Returns the length of the
// longest palindromic
// subsequence in seq
 
// A utility function to get
// max of two integers
// function max( $x, $y)
// { return ($x > $y)? $x : $y; }
 
// Returns the length of the
// longest palindromic
// subsequence in seq
function lps($str)
{
$n = strlen($str);
$i; $j; $cl;
 
// Create a table to store
// results of subproblems
$L[][] = array(array());
 
 
// Strings of length 1 are
// palindrome of length 1
for ($i = 0; $i < $n; $i++)
    $L[$i][$i] = 1;
 
    // Build the table. Note that
    // the lower diagonal values
    // of table are useless and
    // not filled in the process.
    // The values are filled in a
    // manner similar to Matrix
    // Chain Multiplication DP
    // solution (See
    // https://www.geeksforgeeks.org/matrix-chain-multiplication-dp-8/).
    // cl is length of substring
    for ($cl = 2; $cl <= $n; $cl++)
    {
        for ($i = 0; $i < $n - $cl + 1; $i++)
        {
            $j = $i + $cl - 1;
            if ($str[$i] == $str[$j] &&
                            $cl == 2)
            $L[$i][$j] = 2;
            else if ($str[$i] == $str[$j])
            $L[$i][$j] = $L[$i + 1][$j - 1] + 2;
            else
            $L[$i][$j] = max($L[$i][$j - 1],
                             $L[$i + 1][$j]);
        }
    }
 
    return $L[0][$n - 1];
}
 
// Driver Code
$seq = 'GEEKS FOR GEEKS';
$n = strlen($seq);
echo "The length of the " .
      "LPS is ", lps($seq);
 
// This code is contributed
// by shiv_bhakt.
?>

O comprimento do LPS é 7

Consulte o artigo completo em Subsequência Palíndromo Mais Longa | DP-12 para mais detalhes!