题目描述

一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）。

解题思路

补充：也可以用具体结果推算规律

台阶        跳法
  1          1
  2          2
  3          3
  4          5
  5          8
  6         13
  7         21
  8         34
  ...        ... 
规律：前两位的和等于后面的数，属于斐波那契数列

如果只有1级台阶，那显然只有一种跳法。如果有2级台阶，那就有两种跳法：一种是分两次跳，每次跳1级；另一种就是一次跳两级。将n级台阶时的跳法看成n的函数，记为f(n) 。当n>2时，第一次跳的时候就有两种选择：一是第一次只跳1级，此时跳法数目等于后面剩下的n-1级台阶的跳法数目，即f(n-1) ；二是第一次跳2级，此时跳法数目等于后面剩下的n-2级台阶的跳法数目，即f(n-2) 。因此，n级台阶的不同跳法的总数f(n)=f(n-1)+f(n-2) 。因此这实际上就是斐波那契数列问题。

剑指offer实现

class Solution:
    def jumpFloor( number):
        # write code here
        if number <= 0:
            return 1
        elif number <= 2:
            return number
        else:
            a,b = 1,2
            for i in range(2,number):
                tmp = a+b
                a=b
                b=tmp
                #a,b = b,tmp
            return b

本地实现

def fibo(n):
	if n==1 or n==2:
		return n
	return fibo(n-1) + fibo(n-2)
	
if __name__ == "__main__":
	print(fibo(7))  # 21