Build a data-structure which allows O(1) test that s[from..to] is a palindrome. The structure is a 2 x s.size() array: even/odd length times possible center point.

typedef vector<int> V;
string s(4001, ' ');
int n;
V mpl[2]; // maximum palindrome length around i (even and odd lengths)
inline bool is_polindrome(int from, int to){
  assert(0 <= from and from < to and to <= n);
  int eo = (to - from) % 2, c = (from + to) / 2;
  return mpl[eo][c] >= c - from;
}

One can think like that:
Let a(k) be the amount of palindromes in [0,k]. Then we have recursion:
a(k)=MIN{ 1 if [0,k] is pm  , MIN (from i = 0 to k -1) OF a(i) + 1   if [i,k] is pm}
        { 0 else                                          a(i) + k-i else          }

I consider ASK to be absolutely right concerning data structure He proposed.

And implemntataion by this idea =)
http://pastebin.com/6bGHLipR

Considering each character as a pivot, expand on both sides to find the length of both even and odd length palindromes centered at the pivot character under consideration and store the length in the 2 arrays (odd & even).
Time complexity for this step is O(n^2)