I recently started to read abour dynamic programming, and I am doing an exercise on it. The problem to solve: Given a String, find the least amount of palindromes it can be split into, and print out the solution. I found this article on here: Is there an algorithm for checking if a string is a catenation of palindromes?

It helps me, but I dont quite get the last step of the answer: Quote:

Now, you can compute s[1,…,j+1], by checking for each $1\le i\le j−1$ whether s[1,…,i] can be decomposed, and if s[i+1,…,j+1] is a palindrome (using the above 2D table). Giving a $\Theta(n^2)$ time and $\Theta(n^2)$ space algorithm.

What do I do here? I am confused.

  • 1
    $\begingroup$ What have you tried? Do you know dynamic programming? What specifically are you confused about? Have you tried working through a small example to try to fill in the blanks? Have you tried re-reading a textbook chapter on dynamic programming and doing some practice dynamic programming problems from a textbook, to refresh your memory? Did you try posting a comment on that answer? $\endgroup$ – D.W. Jul 18 '14 at 6:00
  • 2
    $\begingroup$ Welcome to Computer Science! Note that you can use LaTeX here to typeset mathematics in a more readable way. See here for a short introduction. $\endgroup$ – FrankW Jul 18 '14 at 6:57
  • 1
    $\begingroup$ There was some confusion in the answer you linked, which DW edited (thanks!). Please re-read and see if that makes sense now. btw, that question deals with "whether a string is a concatenation of non-trivial palindromes", while you want a decomposition into the minimum numbers, possibly including the trivial decomposition (each character is a palindrome in itself). The dynamic programming algorithm in that answer can be modified to maintain the actual number of palindromes in the minimal decomposition of $s[1 \dots j]$ (instead of a boolean Yes/No as in that answer). $\endgroup$ – Aryabhata Jul 18 '14 at 7:01