大家都知道斐波那契数列，现在要求输入一个整数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] = 110         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 + p11             pp = p12             p = cur13         return cur14         # 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