Challenge: The Catalan Numbers
In this lesson, you will solve your first coding challenge using bottomup dynamic programming.
We'll cover the following
Problem statement
The Catalan numbers are a special sequence of numbers given by the following set of formulas:
$C_0 = 1$
$C_n = \sum_{i=0}^{n1} C_iC_{n1i}$
The first expression gives the base case of the formula. The second expression says that the $n^{th}$ Catalan number is simply the sum of products of specific Catalan number pairs. These specific pairs are just Catalan numbers with the same distance from either end of the series.
$C_4$ for example would be equal to:
$C_4 = C_0C_3 + C_1C_2 + C_2C_1 + C_3C_0$
You can already see the hefty amount of recursion in this series.
The Catalan numbers form the following series: (1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862…)
Applications of the Catalan numbers
The Catalan numbers readily appear in many interesting counting problems.

The number of ways to put parentheses around n numbers for multiplication.

The number of paths to climb up a 2n x 2n grid without going above the diagonal.

The number of possible binary trees with n leaf nodes. This has been shown in the visualization below.
Get handson with 1200+ tech skills courses.