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.


closed as unclear what you're asking by D.W., Rick Decker, lPlant, András Salamon, vonbrand Jul 25 '14 at 19:11

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • 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