Dynamic programming algorithm for sentence separation problem?

Question

I have to find a dynamic programming algorithm that solves the following problem, and I seem to be stuck:

Given a function f(w) that returns the frequency at which the word w appears in the English language (0 <= f(w) <= 1), the algorithm divideSentence(s) where s is a string of letters with no spaces must return the value of f(w) of all words in s such that divideSentence is maximised. For example: divideSentence(helloworld) should return f(hello) + f(world)

I understand that with dynamic programming, I can limit the amount of calls to f by storing the intermediate values in say a hashmap, but the way I see it, there are 2^n ways to divide the sentence and I can't see how it's possible to find the solution without trying the 2^n different solutions, because f(hell)+f(o) != f(hello). Although the teacher said it was possible to find an algorithm that finds the solution in O(n²) so clearly I'm missing something...

Can someone point me in the right direction?

visleck visleck · Accepted Answer · 2019-11-30T19:18:37

Here is the dynamic programming solution for the above problem.

Let A[] be the array where A[i] means the answer considering the first i characters. So the final answer will be A[s.length()-1] (considering 0 based indexing) where s is the input string with no spaces.

Now the algorithm is as follows:

for i = 0:n
    for j = 0:i
        A[i]=max(A[i],A[j]+f(s.substring(j+1,i)))
    endfor
endfor

return A[n-1]

where n is the size of input string.
The final answer is stored in A[n-1].

Dynamic programming algorithm for sentence separation problem?

1 Answers