Catalan number follows the formula of (2n)!/(n+1)!n!. The first few Catalan numbers for n = 0, 1, 2, 3, … are 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, …  In this post, we are going to find the n-th Catalan number for any given n. There are 3 solutions. They are iteration, recursion, and dynamic programming.

### Iterative solution

This solution applies the following alternative expression of Cn. It can be implemented with iteration. It has the best time complexity O(n).

## Python

### Recursive solution

This solution uses another alternative expression of Cn. It can be implemented with recursion. It has the worst time complexity O(2^n) with repeated calls.

## Doodle

### Dynamic programming

This solution uses the same expression as recursion. But it overcomes the overlapping in recursion by using dynamic programming technique tabulation. The result from previous calls are saved to a 2d array. They can be re-used for the following steps without calling the recursion. It improves the time complexity from exponential to O(n^2).

## Python

### What are Catalan numbers?

Catalan number follows the formula of (2n)!/(n+1)!n!. The first few Catalan numbers for n = 0, 1, 2, 3, … are 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, …

### What are Catalan numbers used for?

Catalan numbers occur in many counting problems in combinatorics, such as counting the number of ways to generate n pairs of valid parentheses, and counting the number of full binary trees with n+1 leaves.