当前位置: 代码迷 >> 综合 >> 剑指offer之斐波拉契
  详细解决方案

剑指offer之斐波拉契

热度:41   发布时间:2024-01-16 23:51:32.0

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)


  相关解决方案