A very interesting problem! Cut two successive speakers:
A. To determine the palindrome at l to r - d [l] [r] = s [l] == s [r] && d [l +1] [r-1] == 1? A: 0;
0 if it is not a palindrome, a palindrome if. Lazy dynamic)))
Two. To determine the optimal line break at the Palindromes: dp [i] = min (dp [i], dp [ij] +1);
That's all!))
Very pleased with himself))) I should think of such problems)))

Edited by author 16.06.2012 05:40

Edited by author 16.06.2012 05:42