【LeetCode通关全记录】509. 斐波那契数

题目地址：509. 斐波那契数

解法：记忆化搜索（动态规划+状态压缩）

这道题其实最简单的解法是递归，大家应该也都会写，但是递归99%会TLE，所以需要找点省时间的办法。

由于每一个斐波那契数都可以用它的前两个数得出，所以只需要把前两个数存储下来然后循环迭代对应的次数即可求出答案。这其实就是动态规划的一种变体，也可以说是一种“记忆化搜索”，建议看这个：动态规划套路详解，讲的非常非常详细。

当然，这题因为没有涉及求最值（最优子结构），所以不算完整意义上的动态规划，不过和1137一起拿来当动态规划的入门题、跟着前面提到的文章一步一步推出这个空间复杂度为O(1)的解法是再合适不过了。

func fib(n int) int {
	if n == 0 {
		return 0
	}
	if n == 1 {
		return 1
	}
	pre, cur := 0, 1
	for i := 2; i <= n; i++ {
		j := pre + cur
		pre = cur
		cur = j
	}
	return cur
}

执行用时: 0 ms（超过100%的Golang提交记录）

内存消耗: 1.9 MB（超过100%的Golang提交记录）

时间复杂度：O(n)，除了求0和1之外都需要遍历n - 1次才能计算出答案；

空间复杂度：O(1)，只使用了常数个数的存储空间。