Covering string by palindromes

Question

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?

Answer 1

This problem is called minimum palindromic factorization and this problem can be solved in $O(n \log n)$ time, see for example:

A subquadratic algorithm for minimum palindrome factorization by Fici et al

EERTREE: An Efficient Data Structure for Processing Palindromes in Strings by Rubinchik and Shur.