Given a non-empty string s and a dictionary containing a list of unique words, design a dynamic programming algorithm to determine if s can be segmented into a space-separated sequence of one or more dictionary words. if s="algorithmdesign" and your dictionary contains "algorithm" and "design". your algorithm should answer yes as s can be segmented as "algorithmdesign

Let s (i), k denote the substring s (i) s (i+1) ... s k. Let Opt (k) denote whether the sub-string s1, k can be segmented using the words in the dictionary, namely (k) = 1 if the segmentation is possible and 0 otherwise. A segmentation of this sub-string s1, k is possible if only the last word (say si k) is in the dictionary theremaining substring s1, i can be segmented.

Therefore, we have equation:Opt (k) = max Opt (i) 0
We can begin solving the above recurrence with the initial condition that Opt (0) = 1 and then go on to comput eOpt (k) for k = 1, 2. The answer correspond-ing to Opt (n) is the solution and can be computed in Θ (n2) time.