Search⌘ K
AI Features
Home
Courses
Grokking Dynamic Programming Interview in C++

The Catalan Numbers

Explore the concept of Catalan numbers and their recursive formula. Understand naive recursive solutions and improve them with top-down memoization and bottom-up tabulation dynamic programming approaches. Gain skills to optimize time and space complexity for computing Catalan numbers.

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