斐波那契数列

1. 题目描述

大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，第0项为0，第1项是1）。

2. 思路

• 递归
  • 
• 缓存，剔除重复计算
• 动态规划
  • 

3. 实现

3.1. 递归

// 自上往下计算：递归
// 时间复杂度：O(2^n)
// 空间复杂度：递归栈的空间
func Fibonacci(n int) int {
	if n <= 1 {
		return n
	}
	return Fibonacci(n-1) + Fibonacci(n-2)
}

3.2. 缓存

// 为了避免重复计算，可以使用缓存
// 时间复杂度：O（n）， 没有重复的计算
// 空间复杂度：O（n）和递归栈的空间
var cache = make(map[int]int, 0)

func Fibonacci2(n int) int {
	val, ok := cache[n]
	if ok {
		return val
	}

	if n <= 1 {
		return n
	}
	res := Fibonacci2(n-1) + Fibonacci2(n-2)
	cache[n] = res
	return res
}

3.3. 动态规划

// 自下往上计算，动态规划
//时间复杂度：O(n)
//空间复杂度：O（1）
func Fibonacci3(n int) int {
	if n <= 1 {
		return n
	}

	a := 0
	b := 1
	res := a + b
	for i := 2; i < n; i++ {
		a = b
		b = res
		res = a + b
	}

	return res
}

4. 参考

• 斐波那契数列_牛客网
• 509. 斐波那契数 - 力扣（LeetCode）