剑指Offer 10 斐波那契数列

大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，第0项为0）。
n<=39

 1 # -*- coding:utf-8 -*-
 2 class Solution:
 3     def Fibonacci(self, n):
 4         if n == 0:
 5             return 0
 6         if n == 1:
 7             return 1
 8         dp = [0] * (n+1)
 9         dp[1] = 1
10         for i in range(2,n+1):
11             dp[i] = dp[i-1] + dp[i-2]
12         return dp[n]
13         # write code here

矩形覆盖

我们可以用2*1的小矩形横着或者竖着去覆盖更大的矩形。请问用n个2*1的小矩形无重叠地覆盖一个2*n的大矩形，总共有多少种方法？

 1 # -*- coding:utf-8 -*-
 2 class Solution:
 3     def rectCover(self, number):
 4         if number<=2:
 5             return number
 6         dp = [0] * (number+1)
 7         dp[1] = 1
 8         dp[2] = 2
 9         for i in range(3,number+1):
10             dp[i] = dp[i-1] + dp[i-2]
11         return dp[number]
12         # write code here

跳台阶

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

 1 # -*- coding:utf-8 -*-
 2 class Solution:
 3     def jumpFloor(self, number):
 4         if number < 3:
 5             return number
 6         pp = 1
 7         p = 2
 8         cur = pp + p
 9         for i in range(3,number+1):
10             cur = pp + p
11             pp = p
12             p = cur
13         return cur
14         # write code here

变态跳台阶

一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。

1 # -*- coding:utf-8 -*-
2 class Solution:
3     def jumpFloorII(self, number):
4         dp = [1] * (number+1)
5         for i in range(1,number+1):
6             for j in range(1,i):
7                 dp[i] += dp[j]
8         return dp[number]
9         # write code here