304. Program for nth Catalan Number

Given an integer n, print the nth Catalan number - the count of, for example, the number of distinct balanced parenthesizations of n pairs of brackets, or the number of distinct binary search trees with n nodes.

Input: A single line contains the integer n. Output: Print a single integer - the nth Catalan number.

0 <= n <= 30

The closed-form C(2n,n)/(n+1) gives an O(n) alternative (using precomputed factorials) if only ONE specific catalan(n) is needed, versus the O(n²) DP which computes ALL smaller catalan values along the way - useful to mention if only a single large n's value is actually required.

Compute the nth Catalan number - a count appearing in many combinatorial contexts like balanced parentheses and binary search trees. Brute force: Try to directly enumerate all the combinatorial structures being counted (like all balanced parenthesizations) and count them - this is exponential to enumerate directly, when the recursive Catalan formula computes the count without enumeration. Optimised: The Catalan recurrence directly encodes the 'split into a left part and a right part at every possible split point' structure shared by MANY different combinatorial objects (parenthesizations, BSTs, polygon triangulations) - building it bottom-up in a 1D array computes each needed catalan(i) exactly once.

Use the closed-form relationship between Catalan numbers and central binomial coefficients, C(n) = C(2n, n) / (n+1), computed without ever dividing large factorials directly by instead applying the equivalent multiplicative step-by-step recurrence C(i+1) = C(i) * 2*(2i+1) / (i+2), starting from C(0) = 1 and iterating up to C(n). Because each step only involves a constant number of arithmetic operations and depends only on the immediately preceding value, this computes the answer in a single linear loop with just one running value carried forward, no summation or nested loop required. Time: O(n) Space: O(1)

Build an array dp[0..n] from the bottom up using the same recurrence dp[i] = sum over j from 0 to i-1 of dp[j] * dp[i-1-j], with dp[0] = 1, filling each entry using only previously computed (and now cached) smaller entries. Since every dp value is computed exactly once and reused directly from the array for later sums, this eliminates all the redundant recomputation of the naive recursive version, at the cost of an O(n) inner loop for each of the n entries. Time: O(n^2) Space: O(n)

Use the direct recursive definition C(0) = 1 and C(n) = sum over i from 0 to n-1 of C(i) * C(n-1-i), implemented as plain recursive function calls with no caching of intermediate results. Every call to C(k) for k > 1 triggers fresh recursive calls to compute C(0) through C(k-1) all over again, causing the same small values to be recomputed an exponential number of times as n grows, much like naive recursive Fibonacci but with a heavier branching factor. Time: Exponential (roughly O(4^n / n^1.5)) Space: O(n) recursion depth

1. catalan(0)=1; catalan(n) = sum over i from 0 to n-1 of catalan(i)*catalan(n-1-i) - it counts every way to split the outermost structure into a LEFT part of size i and a RIGHT part of size n-1-i. 2. Build a 1D DP array bottom-up from catalan(0), so every catalan(i) needed by the sum is already computed. 3. Catalan numbers also equal C(2n,n)/(n+1), a useful independent formula to double-check the DP result.

Time: O(n²) - for each catalan(n), summing n terms, each requiring already-computed smaller values. Space: O(n), for the catalan array.

Test n = 0 (base case, catalan(0) = 1) and n = 30 (upper bound), where the result is large enough to require a 64-bit-safe accumulation.

Be ready to list at least 2-3 different combinatorial interpretations of Catalan numbers (balanced parentheses count, distinct BST count, valid mountain-range sequences) - recognizing the SAME number appearing across seemingly unrelated counting problems is a hallmark of genuine combinatorial fluency.