Buenas tardes.
En este ejercicio entiendo que la recurrencia está mal definida en la solución, específicamente la parte (3) que establece que:
OPT(i,j) = 2 + OPT (i+1,j-1), cuando 1<=i<j<=n y x_i != x_j
Contraejemplo: x = ABCA
Comienza la recurrencia asumiendo que OPT va a ser mayor o igual que 2, el problema es ese, que ese 2 nunca baja; presupone que "el interior" de x va a ser palíndormo también, y si esto no es así no hay una alternativa.
Entonces se calcularía que
OPT(1,4)
= 2 + OPT (2,3)
= 2 + max { OPT(2,2) , OPT(3,3) }
= 2 + max { 1 , 1 }
= 3
Lo cual es falso.
¿Estoy haciendo el análisis correcto?