Dynamic programming to split a string into a list of separate words

This is basically a dublicate of:

How to split a string into words. Ex: "stringintowords" -> "String Into Words"?

neverthelees, I have in my use a function like: public int Word(x) {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.

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:

for i = 1 to n
   for j=i to n do 
      word(subset of x i to j)

and fill out the table, nevertheless, how on earth will I ever be able to retrieve the optimal solution (in a recursive way?)

any help appreciated.

EDIT: The optimal path is the one with the highest sum of word(x) function, i.e. if we have

a path(1,3)=10 , (3,6)=20, (6,7)=1 , and

a path (1,1)=0 , (2,5)=12, (5,7)=-1

then the sum of the 1st path > 2nd

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

开发者_高级运维cheers!:)

---

Sam you are saying that:

you have a table filled with your position in the string, and booleans for each cell if there is a substring of length j .

example:

                    |       Positions of the example:
                    |            "xdeafcatmonologue"
 -------------------|-------------01234567890123476----------------
length of substring |                              
        1           |             11111111111111111     
        2           |             ------2----------
        3           |             -----3------3----
        4           |             -4--------------- 
        5           |             -----------------
        6           |             -----------------
        7           |             -----------------
        8           |             -----------------
        9           |             --------9--------
                    |              

      final         |             -4---3--9---3----

The dashes are technically zeros, and the numbers potentia and this is the table you will build.

You can build a much smaller table if you only store the maximum value for each position because your Word function tells you the maximum for each position. It doesn't matter if you iterate over substring size, your variable j, because Word does not use j.

Please correct me if I'm mistaken with any of these assumptions.

---

ok let me give you an example:

word thetree


         1  2   3  4  5  6  7 ( ending index)

start 1  1  -1  2 -1 -1 -1 -1
      2  0  1  -1  -1 -1 -1 -1
      3  0  0   1  0  0  0  0
      4  0  0   0  1  0  0  4
      5  0  0   0  0  1  0  0
      6  0  0   0  0  0  1  0  
      7  0  0   0  0  0  0  1

well consider this solution, then if you store each colum individually then at colum number 3 you get 2, and at 7 you get 4, which gives a total of 6, nevertheless, if you take each letter seperately, then : 1+1+1+1+1+1+1= 7 (diagonally down i=j) which means that the talbe is incorrect...

this could work if i could only store the position of the previous entery that was best.(again i think)