Go-Fib-Alternatives

fibos.go

// Brute Force - Recursive O(2^n)
func FibonacciBF(n int) int {
	if n == 1 {
		return 0
	}
	if n == 2 {
		return 1
	}
	return FibonacciBF(n-1) + FibonacciBF(n-2)
}

// DP O(N) - O(N)/space
func FibonacciDP(n int) int {
	fibs := map[int]int{
		1: 0,
		2: 1,
	}

	return cachedFibs(n, fibs)
}
func cachedFibs(n int, fibs map[int]int) int {
	if fib, ok := fibs[n]; ok {
		return fib
	}
	fibs[n] = cachedFibs(n-1, fibs) + cachedFibs(n-2, fibs)
	return fibs[n]
}

// Pre-store O(N) - O(1)/space
func Fibonacci(n int) int {
	fibs := []int{0, 1}

	for i := 2; i <= n; i++ {
		next := fibs[0] + fibs[1]
		fibs = []int{fibs[1], next}
	}
	if n > 1 {
		return fibs[1]
	}
	return fibs[0]
}

// Pre-store O(N) - O(1)/space without map
func fib(n int) int {
	first, second, current := 0, 1, 0
	if n <= 1 {
		return n
	}
	if n == 2 {
		return 1
	}

	for i := 2; i <= n; i++ {
		current = first + second
		first = second
		second = current
	}

	return current
}

// Tribonacci O(N) O(1)
func Tribonacci(n int) int {
	first := 0
	second := 1
	third := 1
	current := 0

	if n == 0 {
		return 0
	}
	if n == 1 || n == 2 {
		return 1
	}

	for i := 3; i <= n; i++ {
		current = first + second + third
		first = second
		second = third
		third = current
	}
	return current
}

// Tribonacci O(N) O(1) cache
type trib struct {
	size   int
	values map[int]int
}

func (t *trib) init() {
	t.size = 38
	t.values = map[int]int{}
	t.values[0] = 0
	t.values[1] = 1
	t.values[2] = 1

	for i := 3; i <= t.size; i++ {
		t.values[i] = t.values[i-1] + t.values[i-2] + t.values[i-3]
	}
}

func TribonacciSpace(n int) int {
	res := trib{}
	res.init()
	return res.values[n]

}