find the nth catalan number in javascript

To find the nth Catalan number in JavaScript, we can use dynamic programming approach with recursion. Catalan numbers can be defined recursively as follows:

C(n) = C(0)*C(n-1) + C(1)*C(n-2) + ... + C(n-1)*C(0)

with base case C(0) = 1.

Here's the code:

index.tsx
function nthCatalanNumber(n) {
  if (n <= 1) return 1;
  
  const dp = new Array(n+1).fill(0);
  dp[0] = 1;
  
  for (let i = 1; i <= n; i++) {
    for (let j = 0; j < i; j++) {
      dp[i] += dp[j] * dp[i-j-1];
    }
  }
  
  return dp[n];
}
243 chars
15 lines

The above code implements the recursive formula using dynamic programming to avoid redundant calculations. We use an array dp of size n+1 to store the values of Catalan numbers.

For a given n, the function iterates from 1 to n and computes each Catalan number using previously computed values, until it computes the nth Catalan number.

Using this function, we can find the nth Catalan number by calling nthCatalanNumber(n).