# Segmenting an English string with no spaces using dynamic programming

Suppose you have a function quality(x) that returns the quality of a sequence of letters x. Given a string such as "howareyoutoday," what is the most efficient way to determine that the segmentation is "how are you today" (i.e. quality(how)+quality(are)+quality(you)+quality(today) is the maximum quality possible)?

I was thinking that we could have something like the following:

A = h, A = o, ..., A[n] = y
Q = quality(A), Q = quality(AA), ..., Q[n] = quality(A...A[n])


Now to determine the segmentation, we find max{Q, .., Q[n]} which will return some Q[i] (the first space is after this). Then, we find max{Q[i+1], .. Q[n]} which returns another Q[i] (second space is after this), etc. until max returns Q[n].

I have some questions though: is this method even correct, and does it use dynamic programming? It seems to me that it does, since we build the initial Q with subproblems to the original problem. Also, is this an optimal solution? To my understanding, the worst case would be O(n^2), which would be when max returns Q, then Q, then Q, etc.

• Without information on quality it's not clear that such an approach can work. Basically, the "Bellman optimality criterion" requires that there's some operation $\circ$ so that $\operatorname{quality}(s) = \operatorname{quality}(s_1 .. s_k) \circ \operatorname{quality}(s_{k+1})$ for some $k$.
– Raphael
Oct 4, 2014 at 12:56
• You should be consider all partitions of the word, not necessary $s_{0,j}$, and next identify the same question, in the subproblems $s_{i_1, i_2}$. Because the string could have characters without sense before appears a real word, and after as well. I think that it's correct vote up for dynamic problem. What's about arxiv.org/pdf/1105.6162.pdf ? Oct 4, 2014 at 23:53