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:
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.
