logo CodeStepByStep logo

catalanNumber

Write a method named catalanNumber that uses dynamic programming to calculate and return a given Catalan number. The Catalan numbers are a combinatoric sequence of integers described by the following formula:

Catalan number formula

Your method accepts an integer k as a parameter and returns the kth Catalan number as a value of type long. The first few Catalan numbers for k = 0, 1, 2, 3, ... are 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, ... See the Wikipedia page linked above in the References area for more insight about formulas for calculating Catalan numbers. You may assume that k is non-negative and that the result will fit into the range of values of type long.

The key constraint of this problem is that you must solve it using a bottom-up dynamic programming approach. Do not use recursion. You are allowed to construct any data structures (array, list, set, map, etc.) necessary to store the data for your dynamic programming algorithm.

Method: Write a Java method as described, not a complete program or class.

You must log in before you can solve this problem.

Log In

Need help?

Stuck on an exercise? Contact your TA or instructor.

If something seems wrong with our site, please

Is there a problem? Contact us.