title: Dynamic programming to split a string into a list of separate words
body: <p>This is basically a dublicate of: </p>
  
  <p><a href="https://stackoverflow.com/questions/3466972/how-to-split-a-string-into-words-ex-stringintowords-string-into-words">How to split a string into words. Ex: &quot;stringintowords&quot; -&gt; &quot;String Into Words&quot;?</a></p>
  
  <p>neverthelees, I have in my use a function like: <code>public int Word(x) {code}</code>, where for a string x,it will return an integer (+ve or -ve), and that integer will be an indication of how good or bad that partitioning is for the specific word. I should return the combination that gives the maximum number.</p>
  
  <p>What I thought of doing for this is to create a table(i,j) , where i and j have length of the word, and fill out the table in tern like: </p>
  
  <pre><code>for i = 1 to n
     for j=i to n do 
        word(subset of x i to j)
  </code></pre>
  
  <p>and fill out the table, nevertheless, how on earth will I ever be able to retrieve the optimal solution (in a recursive way?)</p>
  
  <p>any help appreciated.</p>
  
  <p>EDIT: The optimal path is the one with the highest sum of word(x) function, i.e. if we have <br>
  a path(1,3)=10 , (3,6)=20, (6,7)=1 , and<br>
  a path (1,1)=0 , (2,5)=12, (5,7)=-1 <br>
  then the sum of the 1st path > 2nd</p>
  
  <p>EDIT2: I would like every one to know that this question has been answered by me after long hours of work , nevermind for not getting the solution, getting it yourself is always best i guess:P </p>
  
  <p>cheers!:)</p>