本文主要是介绍剑指offer之斐波拉契，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
1.斐波拉契代码
def f(n):if n <= 0:return 0if n <= 2:return 1one, two = 1, 1for _ in xrange(2, n, 1):one, two = two, one+tworeturn two
2.更多应用
-
青蛙跳台阶
一只青蛙一次可以跳1级台阶，也可以跳2级台阶，求青蛙跳上n级台阶，总共有几种跳法
分析：只有1级台阶,1种跳法，f(1)=1。只有2级台阶，每步1级跳2步或者1步跳2级，共2中跳法，f(2)=2。当有n级台阶时，第一步有2个选择，选择跳1级，此时跳法种数等于后面剩下的n-1级台阶跳法种数，即f(n-1)；选择跳2级，此时跳法种数等于后面剩下的n-2级台阶跳法种数,即f(n-2)。那么合起来就是f(n-1)+f(n-2)。
同理，如果青蛙可以选择跳1级，2级或者3级，那么f(n)=f(n-1)+f(n-2)+f(n-3)
More:如果青蛙可以跳1--n级，随意跳几级，那么f(n)=2^n-1(表示2的n-1次方)
-
矩形覆盖
用8个2X1的小矩形，无重叠的覆盖一个2X8的大矩形,请问有多少种覆盖方法？
分析：我们记2X8覆盖方法为f(8),假设第一个2X1小矩形在最左侧竖着放，右边还剩2X7区域，右边区域的覆盖方法记为f(7).假设第一个2X1小矩形在最左侧横着放，那么左下角必须有一个小矩形也是横着放，剩下的2X6区域有f(6)种方法。显然，由于第一个有2种选择，f(8)=f(7)+f(6)
这篇关于剑指offer之斐波拉契的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
