算。那很容易想到如果我们把计算的结果全都保存下来，按照一定的顺序推出n项，就可以提升效率

解法2：

def f1(n):

    if n==1 or n==2:

        return 1

    l=[0]*n                #保存结果

    l[0],l[1]=1,1            #赋初值

    for i in range(2,n):

        l[i]=l[i-1]+l[i-2]     #直接利用之前结果

    return l[-1]

可以看出，时间o(n)，空间o(n)。

继续思考，既然只求第n项，而斐波那契又严格依赖前两项，那我们何必记录那么多值浪费空间呢？只记录前两项就可以了。

解法3：

def f2(n):

    a,b=1,1

    for i in range(n-1):

        a,b=b,a+b

    return a

补充：

pat、蓝桥杯等比赛原题：求的n很大，F(N)模一个数。应每个结果都对这个数取模，否则：第一，计算量巨大，浪费时间；第二，数据太大，爆内存，

对于有多组输入并且所求结果类似的题，可以先求出所有结果存起来，然后直接接受每一个元素，在表中查找相应答案

此题有快速幂算法，但是碍于篇幅和同学们水平有限，不再叙述，可以自行学习。

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

依旧是找递推关系：

1）跳一阶，就一种方法

2）跳两阶，它可以一次跳两个，也可以一个一个跳，所以有两种

3）三个及三个以上，假设为n阶，青蛙可以是跳一阶来到这里，或者跳两阶来到这里，只有这两种方法。

它跳一阶来到这里，说明它上一次跳到n-1阶，

同理，它也可以从n-2跳过来

————————————————

版权声明：本文为CSDN博主「一只大白兔兔兔兔兔」的原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接及本声明。

原文链接：https://blog.csdn.net/hebtu666/article/details/100585136