Catalan Numbers
A sequence counting balanced-parenthesis strings, distinct BST shapes, polygon triangulations, and more. Each term is a convolution of earlier terms.
- Category
- Dynamic Programming
- Time complexity
- O(n²)
- Space complexity
- O(n)
Pseudocode
C₀ = 1 Cₙ = Σ Cᵢ · Cₙ₋₁₋ᵢ for i in 0..n−1
Reference implementation
C = [1, 1]
for n in range(2, N+1):
C.append(sum(C[i]*C[n-1-i]
for i in range(n)))