Given a string $w=\sigma_1\sigma_2\ldots\sigma_n$, a palindrome cover is a sequence $p_1p_2\cdots p_m$ of words $p_i$ such that $p_1p_2\cdots p_m = w$ and such that each $p_i$ is a palindrome.
How hard is it to find the size minimal palindrome cover? (this seems doable by dynamic programming, but I'm not sure it works).
Does the problem become harder if given as input is also a bound $b$ on each palindrome length?
Consider the simple greedy algorithm, which always takes the longest palindrome which starts at the current location. For example, if $w=1213312$, then it'll output $(121)\cdot(33)\cdot(1)\cdot(2)$, while the optimal cover is $(1)\cdot(213312)$.
Does the greedy algorithm provide 2-approximation for the problem?