一、题目描述
写一个函数，输入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學院 的文章
