Dynamic Programming in Python: Optimizing Programs for Efficiency/

...

/

Solution Review: The Catalan Numbers

Solution Review: The Catalan Numbers

In this lesson, we will review some solutions to the Catalan numbers challenge from the last lesson.

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