## Solutions

# -*- coding:utf-8 -*-
class Solution:
def Fibonacci(self, n):
# write code here
if n <= 0:
return 0
if n == 1:
return 1
return self.Fibonacci(n-1) + self.Fibonacci(n-2)


# -*- coding:utf-8 -*-
class Solution:
def Fibonacci(self, n):
# write code here
if n <= 0:
return 0
if n == 1:
return 1
f1 = 0
f2 = 1
fn = 0
for i in range(2, n + 1):
fn = f1 + f2
f1 = f2
f2 = fn
return fn


## 问题延伸

### 青蛙跳台阶

# -*- coding:utf-8 -*-
class Solution:
def jumpFloor(self, number):
# write code here
if number <= 1:
return 1
f1 = 1
f2 = 1
fn = 0

for i in range(2, number + 1):
fn = f1 + f2
f2 = f1
f1 = fn
return fn


### 变态版青蛙跳台阶

# -*- coding:utf-8 -*-
class Solution:
def jumpFloorII(self, number):
# write code here
if number <= 1:
return 1
return 2 * self.jumpFloorII(number-1)


### 矩阵覆盖

# -*- coding:utf-8 -*-
class Solution:
def rectCover(self, number):
# write code here
if number == 0:
return 0
if number == 1:
return 1
if number == 2:
return 2
f1 = 2
f2 = 1
fn = 0
for i in range(3, number+1):
fn = f1 + f2
f2 = f1
f1 = fn
return fn