面试题10:斐波那契数列
题目描述
大家都知道斐波那契数列,现在要求输入一个整数n,请你输出斐波那契数列的第n项(从0开始,第0项为0)。
n<=39。时间限制:1秒 空间限制:32768K
相关题目:矩形覆盖问题(见文末解析)
解题思路:看到这个题首先想到的是递归呀,学习递归的第一个例子就是这个题。然后一通操作之后发现超时了,题目要求1秒,递归实现的代码放到Visual Studio中调试发现用了3.8秒。在刷LeetCode的时候学习到这个题还有优化的解法,动态规划(DP)解,因为递归需要大量重复的计算,画出二叉树可以看出;而动态规划可以避免重复的计算,因而效率有很大的提升。
解法一(递归):
int Fibonacci(int n)
{
int res;
if(n==0)
res=0;
else if(n==1)
res=1;
else
res=Fibonacci(n-1)+Fibonacci(n-2);
return res;
}
解法二(动态规划DP):
class Solution {
public:
int Fibonacci(int n) {
vector<int> res(n+1,0);
res[0]=0;
res[1]=1;
for(int i=2;i<=n;i++)
res[i]=res[i-1]+res[i-2];
return res[n];
}
};
比较:
#include<iostream>
#include<vector>
#include<ctime>
using namespace std;
int Fibonacci(int n)
{
int res;
if(n==0)
res=0;
else if(n==1)
res=1;
else
res=Fibonacci(n-1)+Fibonacci(n-2);
return res;
}
int Fibonacci_1(int n)
{
vector<int> res(n+1,0);
res[0]=0;
res[1]=1;
for(int i=2;i<=n;i++)
{
res[i]=res[i-1]+res[i-2];
}
return res[n];
}
int main()
{
clock_t start = clock();
int a=Fibonacci(39);
//int a=Fibonacci_1(39);
clock_t end=clock();
cout<<a<<endl<<"花费了"<<(double)(end-start) / CLOCKS_PER_SEC << "秒" << endl;;
return 0;
}
用时长比较:
递归法用时:(3.8秒)
动态规划用时:(不到1秒,回头更精确的测一下多次时间)
相关题目:
矩形覆盖:我们可以用2*1的小矩形横着或者竖着去覆盖更大的矩形。请问用n个2*1的小矩形无重叠地覆盖一个2*n的大矩形,总共有多少种方法?
解法一(动态规划):
class Solution {
public:
int rectCover(int number) {
vector<int> res(number+1,0);
res[1]=1;
res[2]=2;
for(int i=3;i<=number;i++)
{
res[i]=res[i-1]+res[i-2];
}
return res[number];
}
};