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[0] = h, A[1] = o, ..., A[n] = y
Q[0] = quality(A[0]), Q[1] = quality(A[0]A[1]), ..., Q[n] = quality(A[0]...A[n])
Now to determine the segmentation, we find max{Q[0], .., 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[0], then Q[1], then Q[2], etc.
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$. $\endgroup$