The Catalan numbers are an integer sequence that count a large number of things, including the number of ways that n pairs of parentheses can be nested. As an example, two pairs of parentheses can be nested as 0) or (O), so C(2)-2. For our purposes, though, the most important feature of the Catalan numbers is that they satisfy the recurrence C(n) = C(i)C(n-1-i), with a base case of C(0) 1. Answer the following questions about developing a memoized dynamic pro- gramming algorithm to compute the Catalan numbers 1. Give a small example demonstrating why this problem is a good candidate for dynamic programming. 2. What implementation would you recommend for a data structure fora dynamic programming solution to this problem? Justify your answer. 3. Give pseudocode for a memoized dynamic programming algorithm for this problem . What is the worst-case complexity for your algorithm? Justify your an- swer