Calculating Catalan numbers

catalan.py

def catalan_bf(n):
  """
  calculate Catalan number in brute force manner (slow)
  """
  if n == 0:
    return 1
  
  ans = 0
  for k in range(n):
    ans += catalan_bf(k) * catalan_bf(n-1-k)
  return ans

def catalan_dp(n):
  """
  calculate Catalan number using tabulation of dynamic programming
  """
  dp = [0] * (n+1)
  dp[0] = 1

  for m in range(1, n+1):
    for k in range(m):
      dp[m] += dp[k] * dp[m-1-k]
  
  return dp[n]

# test code
if __name__ == "__main__":
  # precalculated Catalan number (see https://oeis.org/A000108)
  catalan6 = 132
  catalan14 = 2674440
  catalan20 = 6564120420

  assert catalan_bf(6) == catalan6
  assert catalan_bf(14) == catalan14
  # assert catalan_bf(20) == catalan20 # (slow!)

  assert catalan_dp(6) == catalan6
  assert catalan_dp(14) == catalan14
  assert catalan_dp(20) == catalan20