There is what 'dynamic programming' is, and there is the 'word segmentation' problem of this thread.
The problem is interesting, and so are algorithms to solve it.
My view is that algorithms to solve the problem are not really dynamic programming.
If strain, then can regard the code I include below to solve the problem as dynamic programming, but can do such things quite generally.
For what 'dynamic programming' is, see the original books by R. Bellman or:
Stuart E.\ Dreyfus and
Averill M.\ Law,
{\it The Art and Theory of Dynamic Programming,\/}
ISBN 0-12-221860-4,
Academic Press,
New York,
1977.\ \
Dimitri P.\ Bertsekas,
{\it Dynamic Programming:
Deterministic and Stochastic Models,\/}
ISBN 0-13-221581-0,
Prentice-Hall,
Englewood Cliffs, NJ,
1987.\ \
George L.\ Nemhauser,
{\it Dynamic Programming,\/}
ISBN 0-471-63150-7,
John Wiley and Sons,
New York,
1966.\ \
Dimitri P.\ Bertsekas and
Steven E.\ Shreve,
{\it Stochastic Optimal Control:
The Discrete Time Case,\/}
ISBN 0-12-093260-1,
Academic Press,
New York,
1978.\ \
E.\ B.\ Dynkin and
A.\ A.\ Yushkevich,
{\it Controlled Markov Processes,\/}
ISBN 0-387-90387-9,
Springer-Verlag,
Berlin,
1979.\ \
Wendell H.\ Fleming and
Raymond W.\ Rishel,
{\it Deterministic and Stochastic Optimal Control,\/}
ISBN 0-387-90155-8,
Springer-Verlag,
Berlin,
1979.\ \
For the word segmentation problem, for some positive integer n, we are given a string of length n of characters of the alphabet, and we are given a dictionary of words. We are to show that the string can be partitioned ('segmented') into a sequence of words in the dictionary or show that no such partitioning exists.
A partitioning is a 'feasible segmentation'. We are only looking for a feasible segmentation and not all feasible segmentations.
Consider the string
'catsdoll'
Okay, the 'substring'
'cat'
is a word. But that word will not be in a feasible segmentation because the string that remains
= 'sdoll'
has no 'feasible segmentation'.
Generally, even if there is a feasible segmentation, just because we have found a word does not mean that that word will be in a feasible segmentation.
Generally we suspect that somehow the solution will be 'iterative', 'incremental', maybe 'recursive'. So, in software terms, we suspect that we will have a do-loop with
i = 1, 2, ..., n
or
i = n, n - 1, ..., 1
For 1 Somehow when we get out of this look we want a feasible segmentation or a claim that there is none.
Let's consider a loop with
i = 1, 2, ..., n
Okay, let's let b(i) = j > 0, i > j, if s[1, i] has a feasible segmentation and let b(i) = 0 otherwise. When b(i) = j, then s[1, j] has a feasible segmentation and s[j + 1, i] is a word in the dictionary.
In the loop, the pass for i gets the value of b(i) and in this uses the values b(j), 1 If we come out of the loop with b(n) = 0 or n = 0, then we conclude that there is no solution.
Fine.
But it's not really dynamic programming. The obvious candidate for 'stages' would be i = 1, 2, ..., n. But in stage i, we have to consider essentially 'stages' 1 But if define the stages, decisions, state transition functions, and optimal value functions in relatively tricky ways, then we might be able to regard the problem as dynamic programming.
Below is some corresponding code. The code is in Rexx which is an elegant old 'scripting' language developed something over 25 years age by Mike Cowlishaw at IBM. It is fair to regard all the elementary values as just strings. If in addition, the strings are legal base 10 numbers, then Rexx can perform arithmetic with up to 50 significant decimal digits.
One special feature is a.x for any string x regarded as an 'index'. Then a.x will be a string.
The code:
/* WORD01.RXS -- */
/* */
/* Solution to 'word segmentation' exercise at */
/* */
/* http://news.ycombinator.com/item?id=2859182 */
/* */
/* Created at 15:40:00 on Monday, August 8th, 2011. */
exec_name = 'word01.rxs'
/* Read dictionary into 'stem' variable dict. from */
/* file in_file: */
in_file = 'dict.dat'
/* Set the 'default' value of 'stem' variable */
/* dict.: */
dict. = 0
Do Forever
If Lines(in_file) = 0 Then Leave
word = Strip( Linein(in_file) )
dict.word = 1
End
/* So, now, a string word is in the dictionary if */
/* and only if dict.word = 1 */
/* The given string to check for a feasible 'word */
/* segmentation' solution is: */
input_string = ''
input_string = 'a'
input_string = 'b'
input_string = 'up'
input_string = 'downup'
input_string = 'down'
input_string = 'downzzzz'
input_string = 'aintgottaword'
input_string = 'gotword'
input_string = 'catsdoll'
input_string = 'therecanbeanotherreasontocontactbefore'
/* Then we find the length of this given string: */
n = Length( input_string )
/* Here is the description of the main logic: For */
/* i = 1, 2, ..., n, we find b.i so that */
/* */
/* / 0, if Substr( input_string, 1, i ) */
/* | has no solution */
/* | */
/* b.i = 0, otherwise. */
/* */
/* When b.i = j > 0, then */
/* */
/* Substr( input_string, 1, j ) */
/* */
/* has a solution and */
/* */
/* Substr( input_string, j + 1, i - j ) */
/* */
/* is a word in the dictionary. */
/* At in b.jm1 below, it is convenient for the */
/* logic to have: */
b.0 = 1
/* Pass through this look determines if */
/* */
/* Substr( input_string, 1, i ) */
/* */
/* has a feasible word segmentation: */
Do i = 1 To n
/* We preemptively set b.i = 0 and then in the */
/* loop on j change the value if appropriate: */
b.i = 0
/* This loop violates the spirit of a dynamic */
/* program with stages i: */
Do j = i To 1 By -1
jm1 = j - 1
If b.jm1 = 0 Then Iterate
word = Substr( input_string, j, i - j + 1 )
If dict.word = 0 Then Iterate
b.i = j
Leave
End
End
/* Since in the loop on i above we had i = 1 To n, */
/* it is essentially inevitable that here we will */
/* have to work from i = n down to 1: */
If b.n = 0 | n = 0
Then
Do
Say "There is no solution."
End
Else
Do
Say 'There is a solution:'
k = 0
i = n
Do Forever
j = b.i
If j = 0 Then
Do
If i = 1 Then Leave
i = i - 1
Iterate
End
k = k + 1
segment.k = Substr( input_string, j, i - j + 1 )
If j = 1 Then Leave
i = j - 1
End
m = k
Do k = m To 1 By -1
Say Format( m - k + 1, 5) segment.k
End
End