Search⌘ K
AI Features
Home
Courses
Grokking Dynamic Programming Interview

The Catalan Numbers

Explore how to calculate the nth Catalan number through the recursive formula and enhance efficiency using dynamic programming patterns like memoization and tabulation. Understand both naive and optimized solutions, their time and space complexities, and apply these methods to common 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 ...