剑指Offer(Python多种思路实现):斐波那契数列
剑指Offer(Python多种思路实现):斐波那契数列
面试10题：
题目：大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项。n<=39
n=0时，f(n)=0 n=1时，f(n)=1 n>1时，f(n)=f(n-1)+f(n-2)
解题思路一：基于循环【推荐】
# 基于循环【推荐】
class Solution:
def Fibonacci(self, n):
small, big=0, 1
if n<=0: return 0
if n==1: return 1
for i in range(2, n+1):
small, big = big, small+big
return small
解题思路二：基于递归
class Solution:
def Fibonacci(self, n):
# write code here
if n<=0:
return 0
elif n==1:
return 1
return self.Fibonacci(n-1)+self.Fibonacci(n-2)
题目拓展2：变态跳台阶
一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
# 变态跳台阶
class Solution:
def jumpFloorII(self, number):
# write code here
if number<=0:
return 0
return 2**(number-1)
题目拓展3：矩形覆盖
我们可以用2*1的小矩形横着或者竖着去覆盖更大的矩形。请问用n个2*1的小矩形无重叠地覆盖一个2*n的大矩形，总共有多少种方法？
# 矩形覆盖
class Solution:
def rectCover(self, n):
if n<=0: return 0
if n==1: return 1
if n==2: return 2
small, big = 1, 2
for i in range(3, n+1):
small, big = big, small+big
return small
作者：雾行
