Nth Catalan Number

Summary

The problem involves calculating the nth Catalan number, which is a sequence of natural numbers that arise in various counting problems. The key concept involved is dynamic programming.

Detailed Explanation

To calculate the nth Catalan number, we can use dynamic programming to optimize our solution. Here's a step-by-step breakdown:

Initialize an array C with n+1 elements, where C[i] will store the ith Catalan number.
Set C[0] = 1, as the 0th Catalan number is by definition 1.
For each i from 1 to n, calculate C[i] using the recurrence relation: C[i] = sum(C[j] * C[k]) for j = 0 to i-1 and k = i-j-1.
Return C[n] as the nth Catalan number.

Here's an ASCII art diagram illustrating the recurrence relation:

    +---------------+
    |      C[3]     |
    +---------------+
           |
           |
       +---------------+
       |  sum(C[j] * C[k])  |
       |  for j = 0 to i-1  |
       |  and k = i-j-1    |
       +---------------+

The time complexity of this solution is O(n^2), as we need to iterate up to n and calculate the sum for each i. The space complexity is O(n), as we need to store the Catalan numbers in an array.

Optimized Solutions

Java

public class NthCatalanNumber { public static int nthCatalan(int n) { int[] C = new int[n + 1]; C[0] = 1; for (int i = 1; i <= n; i++) { C[i] = 0; for (int j = 0; j < i; j++) { C[i] += C[j] * C[i - j - 1]; } } return C[n]; } }