【算法入门07】斐波那契数列

核心考点:空间复杂度,fib理解,剪枝重复计算

大家都知道斐波那契数列,现在要求输入一个正整数n,请你输出斐波那契数列的第n项。
斐波那契数列是一个满足

f i b ( x ) = { 1 x = 1 , 2 f i b ( x − 1 ) + f i b ( x − 2 ) x > 2 fib(x)=\left\{\begin{matrix} 1 & x=1,2\\ fib(x-1)+fib(x-2)&x>2 \end{matrix}\right. fib(x)={ 1fib(x1)+fib(x2)x=1,2x>2

的数列。
​​​​​​​​​​​​​​​​​
解析一:(非常不提倡)

题目已经给出了斐波那契数列的状态转移方程,因此我们可以很容易使用递归的方式来求得第n个斐波那契数。

但如果使用递归来解决该问题,就不得不面对一个问题,那就是大量的重复计算,若是我们要得到第40个斐波那契数,那我们大致需要经历以下路径。
【算法入门07】斐波那契数列_第1张图片
可以看到,图中对于同一斐波那契数进行了多次计算,而且越往下对于同一斐波那契数的重复计算次数越多,因此并不提倡使用递归的方法解决该问题。

//递归
class Solution {
     
public:
	int Fibonacci(int n) {
     
		if (n == 1 || n == 2) //fib(1)=1, fib(2)=1
			return 1;
		return Fibonacci(n - 1) + Fibonacci(n - 2); //fib(n)=fib(n-1)+fib(n-2)
	}
};

解析二:(不提倡)

既然使用递归存在大量的重复计算,那么我们可以考虑将已经计算过的斐波那契数保存起来,这样便避免了斐波那契数的重复计算。

例如,在计算第40个斐波那契数的中途需要计算第38个斐波那契数,而第38个斐波那契数已经被计算过了,那就无需再从此处递归下去了。
【算法入门07】斐波那契数列_第2张图片
从图中看来就是不用再计算二叉树的某一枝叶了,因此该方法被形象的称为“剪枝”。

将递归和剪枝配合起来使用,其时间复杂度相比单纯的递归来说简直快了太多了,但该方法也有一个弊端,那就是需要额外的内存空间来暂时保存已经计算过的斐波那契数。

//递归+剪枝
class Solution {
     
private:
	unordered_map<int, int> filter; //存储已经计算过的斐波那契数
public:
	int Fibonacci(int n) {
     
		if (n == 1 || n == 2) //fib(1)=1, fib(2)=1
			return 1;

		int pper = 0; //第n-2个斐波那契数
		if (filter.find(n - 2) == filter.end())
		{
     
			//在map当中没有找到第n-2个斐波那契数,需要计算
			pper = Fibonacci(n - 2);
			filter.insert({
      n - 2, pper });
		}
		else
		{
     
			//在map当中找到了第n-2个斐波那契数,直接获取
			pper = filter[n - 2];
		}

		int per = 0; //第n-1个斐波那契数
		if (filter.find(n - 1) == filter.end())
		{
     
			//在map当中没有找到第n-1个斐波那契数,需要计算
			per = Fibonacci(n - 1);
			filter.insert({
      n - 1, per });
		}
		else
		{
     
			//在map当中找到了第n-1个斐波那契数,直接获取
			per = filter[n - 1];
		}

		return pper + per; //fib(n)=fib(n-1)+fib(n-2)
	}
};

解析三:(正解)

递归实际上是从终点看向起点,现在我们从起点看向终点,从第一个斐波那契数往后进行计算,需要第几个斐波那契数就计算到第几个。

而在该过程中我们不需要将所有计算过的斐波那契数全部保存起来,因为一个斐波那契数的值只与其前面两个斐波那契数有关。
【算法入门07】斐波那契数列_第3张图片
我们任何时刻只需要保存蓝色方框当中的数据,可以看到蓝色方框的数据是时刻在变化的,因此该方法被形象的称为“动态规划”。

//动规
class Solution {
     
public:
	int Fibonacci(int n) {
     
		if (n == 1 || n == 2) //fib(1)=1, fib(2)=1
			return 1;
		int first = 1; //fib(1)=1
		int second = 1; //fib(2)=1
		int third = 0;
		while (n > 2) //进行n-2次计算
		{
     
			//fib(n)=fib(n-1)+fib(n-2)
			third = first + second;
			first = second;
			second = third;
			n--;
		}
		return third;
	}
};

你可能感兴趣的