509. Fibonacci Number #

package leetcode

import "math"

// Solution One recursive method time complexity O(2^n)，space complexity O(n)
func fib(N int) int {
	if N <= 1 {
		return N
	}
	return fib(N-1) + fib(N-2)
}

// Solution Two bottom-up memoized search time complexity O(n)，space complexity O(n)
func fib1(N int) int {
	if N <= 1 {
		return N
	}
	cache := map[int]int{0: 0, 1: 1}
	for i := 2; i <= N; i++ {
		cache[i] = cache[i-1] + cache[i-2]
	}
	return cache[N]
}

// Solution Three top-down memoized search time complexity O(n)，space complexity O(n)
func fib2(N int) int {
	if N <= 1 {
		return N
	}
	return memoize(N, map[int]int{0: 0, 1: 1})
}

func memoize(N int, cache map[int]int) int {
	if _, ok := cache[N]; ok {
		return cache[N]
	}
	cache[N] = memoize(N-1, cache) + memoize(N-2, cache)
	return memoize(N, cache)
}

// Solution Four optimized dp，saving memory space time complexity O(n)，space complexity O(1)
func fib3(N int) int {
	if N <= 1 {
		return N
	}
	if N == 2 {
		return 1
	}
	current, prev1, prev2 := 0, 1, 1
	for i := 3; i <= N; i++ {
		current = prev1 + prev2
		prev2 = prev1
		prev1 = current
	}
	return current
}

// Solution Five matrix fast exponentiation time complexity O(log n)，space complexity O(log n)
// | 1 1 | ^ n   = | F(n+1) F(n)   |
// | 1 0 |		   | F(n)	F(n-1) |
func fib4(N int) int {
	if N <= 1 {
		return N
	}
	var A = [2][2]int{
		{1, 1},
		{1, 0},
	}
	A = matrixPower(A, N-1)
	return A[0][0]
}

func matrixPower(A [2][2]int, N int) [2][2]int {
	if N <= 1 {
		return A
	}
	A = matrixPower(A, N/2)
	A = multiply(A, A)

	var B = [2][2]int{
		{1, 1},
		{1, 0},
	}
	if N%2 != 0 {
		A = multiply(A, B)
	}

	return A
}

func multiply(A [2][2]int, B [2][2]int) [2][2]int {
	x := A[0][0]*B[0][0] + A[0][1]*B[1][0]
	y := A[0][0]*B[0][1] + A[0][1]*B[1][1]
	z := A[1][0]*B[0][0] + A[1][1]*B[1][0]
	w := A[1][0]*B[0][1] + A[1][1]*B[1][1]
	A[0][0] = x
	A[0][1] = y
	A[1][0] = z
	A[1][1] = w
	return A
}

// Solution Six formula method f(n)=(1/√5)*{[(1+√5)/2]^n -[(1-√5)/2]^n}，using time complexity between O(log n) and O(n)，space complexity O(1)
// After actual testing，you will find that the pow() system function is slower than fast exponentiation，indicating that pow() is slower than O(log n)
// The Fibonacci sequence is a sequence of natural numbers，but the closed-form formula is expressed using irrational numbers。Moreover，when n approaches infinity，the ratio of the previous term to the next term gets closer and closer to the golden ratio 0.618（or rather，the fractional part of the ratio of the next term to the previous term gets closer and closer to 0.618）。
// When computing the Fibonacci sequence with a computer，you can directly use the rounding function Round to compute it。
func fib5(N int) int {
	var goldenRatio float64 = float64((1 + math.Sqrt(5)) / 2)
	return int(math.Round(math.Pow(goldenRatio, float64(N)) / math.Sqrt(5)))
}

// Solution Seven coroutine version，but the time is especially slow，not recommended，placed here only to tell everyone that when writing LeetCode algorithm problems，starting a goroutine is especially slow
func fib6(N int) int {
    return <-fibb(N)
}

func fibb(n int) <- chan int {
    result := make(chan int)
    go func() {
        defer close(result)
        
        if n <= 1 {
            result <- n
            return
        }
        result <- <-fibb(n-1) + <-fibb(n-2)
    }()
    return result
}