Consider the Longest Common Substring (LCS) problem studied in chapter 4. 1. Recall the recursive formula for the optimal subproblem of the LCS 2. Write a code that finds the LCS between two arbitrary strings by using dynamic programming 3. Write a code that finds the LCS between two arbitrary strings by using recursive functions 4. Consider the following two strings: str1 = arsdcsfogmlkmiuoonp and Str2 = ghclppoewmhgfmdsoxzn. Report and compare the numbers of instructions necessary for finding the LCS by the previous two programs. 5. Use the concept of memoization for the second code (with recursive functions) and report the new number of executed instructions. 6. Explain how to find the LCS between three arbitrary strings