c++ - Finding the number of palindromic sequences from a given set of numbers -

suppose given set of numbers 20 40 20 60 80 60 can broken 2 palindromic sequences: 20 40 20, , 60 80 60. can broken 6 palindromic sequences each containing single number.

how find smallest number of palindromic sequences possible given set of numbers in c++?

ps- not homework. genuine question.

a straightforward approach begins looking @ each of o(n³) subsequences , checking see if it's palindrome. once know subsequences palindromic, can dynamic programming in o(n²) time find minimal number of consecutive subsequences cover whole sequence.

for input 20 40 20 60 80 60, c++ implementation below prints [20 40 20] [60 80 60].

#include <cstdio> #include <vector> using namespace std;  int main() {   // read data standard input.   vector<int> data;   int x;   while (scanf("%d", &x) != eof) {     data.push_back(x);   }   int n = data.size();    // @ every subsequence , determine if it's palindrome.   vector<vector<bool> > is_palindrome(n);   (int = 0; < n; ++i) {     is_palindrome[i] = vector<bool>(n);     (int j = i; j < n; ++j) {       bool okay = true;       (int left = i, right = j; left < right; ++left, --right) {         if (data[left] != data[right]) {            okay = false;           break;          }       }       is_palindrome[i][j] = okay;     }   }    // dynamic programming find minimal number of subsequences.   vector<pair<int,int> > best(n);   (int = 0; < n; ++i) {     // check easy case consisting of 1 subsequence.     if (is_palindrome[0][i]) {       best[i] = make_pair(1, -1);       continue;     }     // otherwise, make initial guess last computed value.     best[i] = make_pair(best[i-1].first + 1, i-1);     // @ earlier values see if can improve our guess.     (int j = i-2; j >= 0; --j) {       if (is_palindrome[j+1][i]) {         if (best[j].first + 1 < best[i].first) {           best[i].first = best[j].first + 1;           best[i].second = j;         }       }     }   }    printf("minimal partition: %d sequences\n", best[n-1].first);   vector<int> indices;   int pos = n-1;   while (pos >= 0) {     indices.push_back(pos);     pos = best[pos].second;   }   pos = 0;   while (!indices.empty()) {     printf("[%d", data[pos]);     (int = pos+1; <= indices.back(); ++i) {       printf(" %d", data[i]);     }     printf("] ");     pos = indices.back()+1;     indices.pop_back();   }   printf("\n");    return 0; }