动态规划学习之三种方法解决斐波拉契数

斐波拉契数是一个很经典的问题，也会很多公司面试的考题，每个学习计算机的同学都会接触这个问题，尤其是在学习递归的时候，利用递归来解决斐波拉契数是很多教材采用的一个例子，所以很多同学一想到斐波拉契马上就会采用递归，递归貌似简单，但是效率真的很高吗？不然！下面是我在学习动态规划的过程中总结的集中解决斐波拉契数的不同方法：

一、最野蛮最原始的方法

long f0(int n)
{
	if (n == 0 || n == 1)
		return n;
	else
		return F(n - 1) + F(n - 2);
}

这是最直接的递归方式，其时间复杂度为O(1.618^n)，是一个指数时间级的算法，当n超过30时，你就慢慢等待吧，运气差的话直接死机了。

二、自底向上的动态规划方法

我们已知F(0)和F(1)的值，则我们从F(2)开始就可以利用前面两个已经计算出来的值，这样从小到大就可以最终求出F(n)

long F(int n)
{
	long f1,f2,k,t;
	if(n < 2) return n;
	f1 = f2 = 1;
	for (k = 2; k < n; k++)
	{
	<span style="white-space: pre;">	</span>t = f1 + f2;
		f1 = f2;
		f2 = t;
	}
	return t;
}

其时间复杂度已经从指数级降到线性级O(n)了，空间复杂度为O(1)

三、自顶向下的动态规划方法

这种方法也是采用递归的思想，但是确应用了动态规划的原理：将以前的计算结果存储起来备用，这样在以后出现同样的问题时就不用重复计算。也叫备忘录方法。

int fib[1000] = {0};
long f1(int n)
{
	int t;
	if(fib[n] != 0) return fib[n];
	if(n == 0) t = 0;
	if(n == 1) t = 1;
	if(n > 1) t = f1(n-1) + f1(n - 2);
	return fib[n] = t;
}

自顶向下的动态规划递归方法大大减少了递归调用的次数，避免了重复递归计算，其算法时间复杂度也为线性级，其关键就是能够"保存已经计算过的子问题的结果".