Search⌘ K
Home
Courses
Grokking Dynamic Programming Interview in Python

The Catalan Numbers

Explore the calculation of Catalan numbers by implementing both naive and dynamic programming solutions. Understand the recursive definition and learn to optimize it using memoization and tabulation, reducing time complexity from exponential to polynomial. This lesson guides you through computing Catalan numbers efficiently for use in combinatorial problems.

We'll cover the following...

Statement

Given a number n, find the nthn^{th} Catalan number.

Catalan numbers are a special sequence of numbers given by the following set of formulas:

C0=1C_0 = 1

Cn=∑i=0n−1CiCn−1−iC_n = \sum_{i=0}^{n-1} C_iC_{n-1-i}

The first expression gives the base case of the formula. The second expression says that the nthn^{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.

C4C_4 for example would be equal to:

C4=C0C3+C1C2+C2C1+C3C0C_4 = C_0C_3 + C_1C_2 + C_2C_1 + C_3C_0 ...