Dont write a code.

For part b) use Dynamic Programming to solve the question.

Q2) Given a string of characters without any spaces between them and a dictionary of valid English words, find all possible ways to break the string in individual dictionary words. Examples: dictionary ["I","have", "Sam", "am", "this", "dog" String "IamSam" Output: "I am Sam" String "iadog" Output:String can't be broken a) Design the recursive sub-problem condition(s) Use your solution in (a) to solve the following problems: You have to show the complete solution of the DP steps either by top down or bottom-up approach. b) dictionary ["I", "KU", "study", "CpE", "in'"] 1t string input: "IstudyCpEinKU" nd string input: "IstudyEEinKU" c) What is the running time of your algorithm? Note: your solution must not run in exponential time