题目：现在要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，第0项为0，第1项是1）。n<=39
以下来自baidubaike：
|
经过月数
|
0
|
1
|
2
|
3
|
4
|
5
|
6
|
7
|
8
|
9
|
10
|
11
|
12
|
|
总体对数
|
0
|
1
|
1
|
2
|
3
|
5
|
8
|
13
|
21
|
34
|
55
|
89
|
144
|
则斐波那契束列的通项为：
f(0)=0, f(1)=1, f(n)=f(n-2)+f(n-1)
把其翻译成代码则可以用递归的方式：
def Fibonacci(self, n): # write code here if n==0: return 0 if n==1: return 1 res=Fibonacci(n-2)+Fibonacci(n-1) return res
但是这种方法在时间复杂度上会有很大问题，由f(5)=f(4)+f(3),可有f(4)=f(3)+f(2)和f(3)=f(2)+f(1)，可以看到每个f(x)被多次计算，如果求第n个数列值，则要计算次数为2的n次方。我们可以用一个数组保存每个值，避免重复运算。但是其实每次计算都只会用到上次两个数相加之和及两个数中较大者，没必要保存每个值。
# -*- coding:utf-8 -*- class Solution: def Fibonacci(self, n): # write code here if n==0: return 0 if n==1: return 1 a=0 b=1 res=0 for i in range(0,n-1): res=a+b a=b b=res return res
如果求的是f(2)，则for循环只执行一次得到的res就是所求，因此求第n项的过程需要n-1次循环，故有range(0,n-1)【表示i=0~n-2，共n-1个】，时间复杂度O(n-1)约等于O(n)，比上面的递归快了很多。
扩展：青蛙跳台阶
一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）。
当青蛙在第n个台阶，它可能是从n-1跳一阶过来的，也可能是从n-2跳两阶，数列通项为 f(n)=f(n-2)+f(n-1)，和费切那波数列类似，但是初始值不一样。
class Solution: def jumpFloor(self, n): # write code here if n==1: return 1 if n==2: return 2 a=1 b=2 res=0 for i in range(0,n-2): res=a+b a=b b=res return res
拓展：变态跳台阶问题
一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
当一个青蛙在n台阶的时候，它可能是从n-1跳一阶过来的，可能是从n-2跳二阶过来的，可能是从n-3跳三阶过来的......令f(n)为跳到n的跳法总数，则可以推理出f(n)=f(n-1)+f(n-2)+f(n-3)+......+f(1)，f(n-1)=f(n-2)+f(n-3)+......+f(1)，联立两项能发现f(n)=2*f(n-1)，这就是通项了。
# -*- coding:utf-8 -*- class Solution: def jumpFloorII(self, n): # write code here if n==1: return 1 a=1 res=0 for i in range(2,n+1): res=a*2 a=res return res
原文：https://www.cnblogs.com/zhangmora/p/12803828.html