Function NthCatalanNumber

dynamic/catalan.go:15–33

NthCatalan returns the n-th Catalan Number Complexity: O(n²)

(n int)

// NthCatalan returns the n-th Catalan Number
// Complexity: O(n²)
func NthCatalanNumber(n int) (int64, error) {
	if n < 0 {
		//doesn't accept negative number
		return 0, errCatalan
	}

	var catalanNumberList []int64
	catalanNumberList = append(catalanNumberList, 1) //first value is 1

	for i := 1; i <= n; i++ {
		catalanNumberList = append(catalanNumberList, 0) //append 0 and calculate

		for j := 0; j < i; j++ {
			catalanNumberList[i] += catalanNumberList[j] * catalanNumberList[i-j-1]
		}
	}

	return catalanNumberList[n], nil
}