We want to devise a dynamic programming solution to the following problem: there is a string of characters which might have been a sequence of words with all the spaces removed, and we want to find a way, if any, in which to insert spaces that separate valid English words.

1 Description We want to devise a dynamic programming solution to the following problem: there is a string of characters which might have been a sequence of words with all the spaces removed, and we want to find a way, if any, in which to insert spaces that separate valid English words. For example, youth event could be from "the you the vent" the youth event" or "they out he vent". If they the input is theeaglehaslande, then there's no such way. Your task is to implement a dynamic programming solution in two separate ways iterative bottom-up version recursive memoized version Assume that the original sequence of words had no other punctuation (such as periods), no capital letters, and no proper names all the words will be available in a dictionary file that will be provided to you Let the input string be z r122...an. We define the subproblem splits (i) as that of determining whether it is possible to correctly add spaces to rizi+1...acm. Let dict(a) be the function that will look up a provided word in the dictionary, and return true iff the word w is in it. A recurrence relation for split is given below: if i n 1 true split(i) Obviously, split(i) only finds out whether there's a sequence of valid words or not. Your pro- grama must also find at least one such sequence. The program will read a text file from standard input. For example, if you have a Java class named dynProg, the command java dynProg insample.txt is what you would use to run your program. The name of the dictionary file should be hardwired in the code. We will be testing your program on a file named "diction 10k.txt" 2 Sample Input The first line of input is an integer C. This is followed by C lines, each containing a single string, representing a phrase to be tested