9.md

剑指Offer之面试题9：斐波那契数列

题目1：写一个函数，输入n，求斐波那契数列的第n项。

1 方法1：递归

斐波那契数列本身就是用递归来定义的，因此，许多教科书上就用递归来实现。

long long fibonacci(unsigned int n)
{
	if(n <= 0) {
		return 0;
	}

	if(n == 1) {
		return 1;
	}

	return fibonacci(n - 1) + fibonacci(n - 2);
}

2 方法2：循环(动态规划)

书上通过分析fibonacci(10)展示了这种方法的问题：同一个中间结果多次计算。其实，这跟动态规划中的重叠子问题是一样的：当同一个中间结果多次计算时，可以保存中间结果的值，从而减低时间复杂度。

long long fibonacci(unsigned int n)
{
	if(n <= 0) {
		return 0;
	}

	if(n == 1) {
		return 1;
	}

	long long fib1 = 0;
	long long fib2 = 1;
	long long fibn = 0;

	for(unsigned int i = 2; i <= n; ++i) {
		fibn = fib1 + fib2;
		fib1 = fib2;
		fib2 = fibn;
	}

	return fibn;
}

3 问题延伸

有些问题，虽然表面看起来跟斐波那契数列没什么关系，但是，经过分析之后，它就是个斐波那契数列。

一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法。

解法：当只有1级台阶时，只有1种跳法。当只有2级台阶时，有两种跳法。当有n级台阶时，可以先跳1级，然后求得剩下n-1级台阶的跳法，也可以先跳2级，然后求得剩下n-1级台阶的跳法。于是有：

• f(n) = 1; n = 1
• f(n) = 2; n = 2
• f(n) = f(n - 1) + f(n - 2); n > 2