Given a string S[1, . . . , n] and a dictionary of strings S, return true if S[1, . . . , n] can be segmented into a space-separated sequence of one or more dictionary words. Note that the same word...

Given a string S[1, . . . , n] and a dictionary of strings S, return true if S[1, . . . , n] can be segmented into a space-separated sequence of one or more dictionary words. Note that the same word in the dictionary may be reused multiple times in the segmentation.

Precisely define the subproblem.
Provide the recurrence equation.
Describe the algorithm in pseudocode to compute the optimal value.
Describe the algorithm in pseudocode to print out an optimal solution.