find the nth catalan number in go

Here's a Go function that finds the nth Catalan number using dynamic programming:

main.go
func catalanDP(n int) uint64 {
    // Initialize a slice for storing previously calculated Catalan numbers
    catalan := make([]uint64, n+1)
    catalan[0] = 1
 
    // Fill the slice using dynamic programming
    for i := 1; i <= n; i++ {
        for j := 0; j < i; j++ {
            catalan[i] += catalan[j] * catalan[i-j-1]
        }
    }
 
    return catalan[n]
}
370 chars
15 lines

This function uses the fact that the nth Catalan number can be computed using the formula Cn = (2n)! / ((n+1)! * n!), which can also be expressed recursively as Cn = sum(Ci * Cn-i-1) for i in [0, n-1]. However, using dynamic programming is more efficient than recursion for larger values of n.

The function initializes a slice of length n+1 to store previously calculated Catalan numbers. It then fills the slice using nested loops, computing each Catalan number by summing the products of two previously computed Catalan numbers. It finally returns the nth Catalan number.