Search⌘ K
AI Features
Home
Courses
Dynamic Programming in Python: Optimizing Programs for Efficiency

Solution Review: The Catalan Numbers

Understand how to compute Catalan numbers using recursive, top-down memoized, and bottom-up dynamic programming methods. Learn to optimize time from factorial to quadratic complexity and manage space efficiently. This lesson prepares you to implement DP solutions for combinatorial problems.

We'll cover the following...

Solution 1: Simple recursion #

Python 3.5
def catalan(n):
  if n == 0:      # base case; C(0) = 1
    return 1
  sum = 0
  # iterate from 1...n to evaluate: C(0)*C(n-1) + C(1)*C(n-2) ... + C(n-1)*C(0)
  for i in range(n):  
    sum += (catalan(i) * catalan(n-1-i))  # C(i)*C(n-1-i)
  return sum
print(catalan(4))

Explanation

This is a much simpler problem. The only thing we need to figure out is how to convert the following summation equation into code:

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

or

Cn=C0Cn−1+C1Cn−2+C2Cn−3+...+Cn−1C0C_n = C_0C_{n-1} + C_1C_{n-2} + C_2C_{n-3} + ... + C_{n-1}C_0 ...