Question

Do the following problem by developing a dynamic programming algorithm for it:

Describe efficient algorithms for the following variants of the text segmentation problem. Assume that you have a subroutine IsWord that takes an array of characters as input and returns True if and only if that string is a “word”. Analyze your algorithms by bounding the number of calls to IsWord.

Given an array A[1 .. n] of characters, compute the number of partitions of A into words. For example, given the string ARTISTOIL, your algorithm should return 2, for the partitions ARTIST·OIL and ART·IS·TOIL.

Answer 1

for array A[1,2,3......n] if last k symbols form a "word" the the problem is reduced into subproblem of finding partitions in A[1,2.....k-1]

let DP[i] denotes the number of valid word partition in A[1,2,3.....i]

Then the recurrenve relation is just:

Algorithm:

for i=1 to n:

    for k=i to 1

    Dp[i]=DP[i]+Word(A[k,k+1.......i])*DP[k-1]

return DP[n]

Time complexity: when i=1 inner loop runs for 1 time , when i=2 inner loop runs for 2 times and 3 times when i=3 and so on:

so total is 1+2+3+4.......+n =O(n^2)