剑指offer07--斐波那契数列
题目描述
大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，第0项为0，第1项是1）。
n\leq 39n≤39
思路
1.递归：f(n)=f(n-1)+f(n-2)
2.动态规划：递归重复计算太多次，从01开始用两个变量记录，就不用反复计算
实现
递归
class Solution {
public:int Fibonacci(int n) {if (n==0) return 0;if (n==1) return 1;return Fibonacci(n-1)+Fibonacci(n-2);}
};
经过测试，最大的n=42，再增加就超时了。
动态规划
class Solution {
public:int Fibonacci(int n) {if (n==0) return 0;if (n==1) return 1;int f=0,b=1;for (int i=1;i<n;i++){int m=f+b;f=b;b=m;}return b;}
};
经过测试，最大的n=61，再增加就溢出了（int）。
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！