find the nth catalan number in ruby

The Catalan numbers are a sequence of positive integers that appear in many problems of discrete mathematics, such as counting the number of ways to parenthesize an expression, or the number of full binary trees with n internal nodes. The nth Catalan number can be computed recursively using the formula C(n) = C(0)C(n-1) + C(1)C(n-2) + ... + C(n-1)C(0). Here's how you can use dynamic programming and memoization to implement a Ruby program that computes the nth Catalan number efficiently:

main.rb
# Memoize the Catalan numbers to avoid recomputing them
$catalan = [1]

# Compute the nth Catalan number using dynamic programming and memoization
def catalan(n)
  if $catalan[n]
    return $catalan[n]
  end

  # Compute the nth Catalan number using the recursive formula
  c = 0
  for i in 0..n-1
    c += catalan(i) * catalan(n-1-i)
  end

  # Store the result in the memoization table
  $catalan[n] = c
  return c
end

# Example usage
puts catalan(0)  # => 1
puts catalan(1)  # => 1
puts catalan(2)  # => 2
puts catalan(3)  # => 5
puts catalan(4)  # => 14
puts catalan(5)  # => 42
584 chars
28 lines

This program uses a memoization table $catalan to store the Catalan numbers computed so far. The catalan(n) function first checks if the nth Catalan number has already been computed and stored in the memoization table, and if so, returns it. Otherwise, it uses the recursive formula to compute the nth Catalan number by summing up the products of each pair of Catalan numbers from C(0) to C(n-1). Finally, it stores the result in the memoization table and returns it.