find the nth catalan number in csharp

The nth Catalan number can be found using recursion, dynamic programming, or memoization. Here are the code snippets for each approach:

Recursion:


main.cs
public static long CatalanRecursion(int n)
{
    if (n <= 1)
    {
        return 1;
    }
    long res = 0;
    for (int i = 0; i < n; i++)
    {
        res += CatalanRecursion(i) * CatalanRecursion(n - i - 1);
    }
    return res;
}
237 chars
14 lines

Dynamic Programming:


main.cs
public static long CatalanDp(int n)
{
    long[] dp = new long[n + 1];
    dp[0] = dp[1] = 1;
    for (int i = 2; i <= n; i++)
    {
        for (int j = 0; j < i; j++)
        {
            dp[i] += dp[j] * dp[i - j - 1];
        }
    }
    return dp[n];
}
259 chars
14 lines

Memoization:


main.cs
public static long CatalanMemoization(int n, long[] memo)
{
    if (n <= 1)
    {
        return 1;
    }
    if (memo[n] != 0)
    {
        return memo[n];
    }
    long res = 0;
    for (int i = 0; i < n; i++)
    {
        res += CatalanMemoization(i, memo) * CatalanMemoization(n - i - 1, memo);
    }
    memo[n] = res;
    return res;
}
345 chars
19 lines

And here is how you can call these functions:


main.cs
int n = 5;
Console.WriteLine(CatalanRecursion(n));
Console.WriteLine(CatalanDp(n));
Console.WriteLine(CatalanMemoization(n, new long[n + 1]));
143 chars
5 lines