Please use the Python program

We want to devise a dynamic programming algorithm for the following problem: there is a string of characters which might have been a sequence of English words with all the spaces removed, and we want to find a way, if any, in which to insert spaces that separate English words. For example, theyouthevent could be the you the vent, the youth event or they out he vent. If the input is theeaglehaslande, then there's no such way; note that the eagle has lande does not count, because "lande is not an English word. Your task is to implement a dynamic programming algorithm (in a bottom-up manner). Assume that the original sequence of characters have no other punctuation such as periods, no capital letters, and no proper names that is, all the English words will be available in a dictionary file that will be provided to you. Let the input string be x = [112...In. We define the subproblem split(i) as that of determining whether it is possible to correctly add spaces to rilit1...In. Let dict(w) be the function that will look up a provided word in the dictionary, and return true if and only if the word w is in it. A recurrence relation is given below: true if i = n +1 = V7-(dict(+1...A Obviously, split(i) only finds out whether there's a sequence of valid English words or not. Your program must also find and display 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