斐波拉契数列解法归纳

一、题目描述

写一个函数，输入n，求斐波拉契数列的第n项。斐波拉契数列定义如下：

f(n) = {

0             n=0

1             n=1

f(n-1)+f(n-1) n>1

       }

二、解题思路

【解法一】常规递归

不足：此法不推荐，原因是会产生大量重复的计算，而且重复的结点会随着n的增大而急剧增加。

事实上，用递归方法计算的时间复杂度是以n的指数方法递增的

【解法二】带备忘录的递归

此法在解法一的基础上加了一个存储，避免了大量重复结点的计算，比法一效率高很多

【解法三】动态规划

此题满足动规的特点：新问题依赖子问题。于是考虑可自底向上的思考方式：

首先根据f(0)和f(1)得到f(2)

然后根据f(1)和f(2)得到f(3)

...

以此类推，最后得到f(n),可保证一次for循环得出结果，所以复杂度为O(n)

三、算法实现

方法1：常规递归--不推荐

方法2：带备忘录的递归

方法3：动态规划

本文来自CSDN博客：https://blog.csdn.net/qiki_tangmingwei/article/details/80852946