title: Split a string to a string of valid words using Dynamic Programming
body: <p>I need to find a dynamic programming algorithm to solve this problem. I tried but couldn't figure it out. Here is the problem:</p>
  
  <p>You are given a string of n characters s[1...n], which you believe to be a corrupted text document in which all punctuation has vanished (so that it looks something like "itwasthebestoftimes...").  You wish to reconstruct the document using a dictionary, which is available in the form of a Boolean function dict(*) such that, for any string w, dict(w) has value 1 if w is a valid word, and has value 0 otherwise.</p>
  
  <ol>
  <li>Give a dynamic programming algorithm that determines whether the string s[*] can be reconstituted as a sequence of valid words.  The running time should be at most O(n^2), assuming that each call to dict takes unit time.</li>
  <li>In the event that the string is valid, make your algorithm output the corresponding sequence of words. </li>
  </ol>