1. Suppose that you have two strings, Si, S2, each consisting of characters from some small alphabet. The lengths of the strings are k and n respectively. You can assume that n 2 k but not that k is necessarily some small value. If we alternate reading characters from one string and then the other, we create a "blend" of the two strings. For example if and we can create this blend: DYNAMICPROGRAMMINGISSOAMAZING Note that the length of a blend is n+k, and there can be many blends Now for the problem: Given three strings Si, S2 and C, determine if C is a blend of Si and S2. If Si and S2 have size k and n respectively, the time complexity should be O(kn) You should address the following in your answer: Formulate the problem recursively, including an informal justification for its correct ness. (How can you categorize subproblems that will be helpful to solve first?) How many distinct subproblems are there? Mention what you consider to be a base case. What is the size of the dynamic programming table that you will use, how do you fi it in, and where are the base cases and final answer located? 1. Suppose that you have two strings, Si, S2, each consisting of characters from some small alphabet. The lengths of the strings are k and n respectively. You can assume that n 2 k but not that k is necessarily some small value. If we alternate reading characters from one string and then the other, we create a "blend" of the two strings. For example if and we can create this blend: DYNAMICPROGRAMMINGISSOAMAZING Note that the length of a blend is n+k, and there can be many blends Now for the problem: Given three strings Si, S2 and C, determine if C is a blend of Si and S2. If Si and S2 have size k and n respectively, the time complexity should be O(kn) You should address the following in your answer: Formulate the problem recursively, including an informal justification for its correct ness. (How can you categorize subproblems that will be helpful to solve first?) How many distinct subproblems are there? Mention what you consider to be a base case. What is the size of the dynamic programming table that you will use, how do you fi it in, and where are the base cases and final answer located