算法｜”兔子数列“ 你会了吗？

我正在参加「兔了个兔」创意投稿大赛，详情请看：「兔了个兔」创意投稿大赛

兔子数列

"兔子数列" 其实就是斐波那契数列（Fibonacci sequence），又称黄金分割数列。因为数学家列昂纳多·斐波那契以兔子繁殖为例子。斐波那契数列是一个经典的黄金分隔数列：

开始时有0只兔子，第一个月1只兔子，第二个月1只兔子，第三个月2只兔子，之后的每一个月的兔子都等于前2个月的兔子总和。所以它的数列是：0、1、1、2、3、5、8、13、21……

递归解法

根据以上规律，可以总结出它的函数方程式。

F(0)=0

F(1)=1

F(n)=F(n - 1)+F(n - 2)

有了函数方程式，使用 Go 语言简单实现一个函数来计算斐波那契数列就比较简单了：

func Fibonacci(n int) int {
    if n < 0 {
       return 0
    }
    if n == 0 {
       return 0
    }
    if n == 1 {
       return 1
    }
    return Fibonacci(n-1) + Fibonacci(n-2)
 }

通过递归的方式实现了斐波那契数列的计算。可以看出时间复杂度T(n)=T(n-1)+T(n-2)，即为O(2^N),指数级别的，空间复杂度O(n)。

在面试的时候如果面试官进一步提问你是否有更优的解决的方法时，可以学学“动态规划”

动态规划解法

使用递归方法解决时存在大量重复的函数调用，导致效率低。那么使用动态规划来解决，每次都保存上一个子问题的解，从而避免重复求解子问题。即求第n项的值时，只需要保存n-1项和n-2项的值，这样就可以提高效率。所以可以使用2个变量每次都保存下上一次和上上一次的结果。

func Fibonacci(n int) int {
	if n < 2 {
		return n
	}

	p := 0
	q := 0
	r := 1
	for i := 2; i < n; i++{
		p = q
		q = r
		r = p + q
	}
	return r
}

这里主要是增加了空间存储上一次结果，就避免了重复的计算的方式提高计算效率。时间复杂度是O(n),空间复杂度是O(n)。

动态规划其实就是将一个问题划分成多个子问题，然后每个子问题的最优解决定了当前问题的最优解。所以在解决此类问题的时候最重要的是找出最优子问题解。那么如何判断一个问题能不能用动态规划来解决主要根据2个属性：最优子结构和重叠子问题。

所以，你学会了吗？