I have got WA 23, but I know that my algo will have TLE...
What is the right algo???

Accepted!!!!
BFS - very good thing!!!!

#include <iostream>
#include <algorithm>
#include <string>

unsigned counter = 0;
void printPalindroms(unsigned short *splitIndex, unsigned short i, const std::string& str){
    if(splitIndex[i] == 0){
        std::cout<<str.substr(0, i+1)<<" ";
    }else{
        printPalindroms(splitIndex, splitIndex[i]-1, str);
        std::cout<<str.substr(splitIndex[i], i + 1 - splitIndex[i])<<" ";
    }
}

int main()
{
    std::string strr;
    std::cin>>strr;
    const char* str = strr.data();

    unsigned length = strr.size();
    unsigned arrSize = (length*length + length)/2;
    bool *pArrData = new bool[arrSize];
    bool **pArr = new bool*[length];

    unsigned short *splitWeights = new unsigned short [length];
    unsigned short *splitIndex = new unsigned short[length];

    std::fill(pArrData, pArrData + arrSize, false);
    std::fill(splitWeights, splitWeights + length, length +2);
    std::fill(splitIndex, splitIndex + length, 0);

    unsigned offset = 0;
    for(unsigned i = 0; i<length; ++i){
        pArr[i] = pArrData + offset;
        offset += length - i;
    }

    // init the first row
    std::fill(pArr[0], pArr[0] + length, true);

    //init the second row
    for(unsigned i = 0; i<length - 1; ++i){
        if(str[i] == str[i+1]){
             pArr[1][i] = true;
        }
    }

    for(unsigned i = 2; i < length; ++i){
        for(unsigned j = 0; j< length - i; ++j){
            if(pArr[i-2][j+1] && str[j] == str[j+i]){
                pArr[i][j] = true;
            }
        }
    }

    for(unsigned  i = 0; i < length; ++i){
        if(pArr[i][0] == true){
            splitWeights[i] = 0;
            splitIndex[i] = 0;
        }else{
            for(unsigned j = 1; j <= i; ++j){
                if(pArr[i-j][j]){
                    unsigned short temp = splitWeights[j-1] + 1;
                    if(temp < splitWeights[i]){
                        splitWeights[i] = temp;
                        splitIndex[i] = j;
                    }
                }
            }
        }
    }

    std::cout<<splitWeights[length -1] + 1<<std::endl;

    printPalindroms(splitIndex, length - 1, strr);

    delete[] splitIndex;
    delete[] splitWeights;
    delete[] pArr;
    delete[] pArrData;


    return 0;
}