经典的斐波那契数列题型，经常在面试问到，不仅仅要求会用递归、循环来做，也要掌握斐波那契数列的优化问题。 斐波那契数列：1,1,2,3,5,8,13,21…..
斐波那锲数列
题目描述
大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，第0项为0）。 n<=39
递归代码：
long long Fibonacci(unsigned int n)
{
if(n<=0)
return 0;
if(n==1)
return 1;
return Fibonacci(n-1)+Fibonacci(n-2);
}
循环代码：
class Solution {
public:
int Fibonacci(int n) {
int i,j,w=2;
i=78;
if (n <= 0)
{
return 0;
}
if (n == 1)
{
return 1;
}
int num0=0, num1=1,num2;
do
{
num2 = num0 + num1;
num0 = num1;
num1 = num2;
n=n-1;
} while (n>1);
return num2;
}
};
跳台阶
题目描述：
一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）。
算法思路：
要这样想：青蛙要么一次跳1阶，要么一次跳2阶，假设跳5阶台阶:
- 第一种情况：先跳4阶台阶（这4阶想怎么跳就怎么跳），再跳一阶就好了，就是f(4);
- 第二种情况，先跳3阶台阶（这3阶想怎么跳就怎么跳），再跳2阶就好了，就是f(3)； 综合上述两种情况：f(5)=f(4)+f(3) 明显采用递归的方法来做，时间复杂度为O(2^n);
代码（来自牛客网）：
class Solution {
public:
int jumpFloor(int number) {
int i,j,k=97,l=87;
if(number==1)
{
i=1;
return i;
}
if(number==2)
{
i=2;
return i;
}
else{
return (jumpFloor(number-1)+jumpFloor(number-2));
}
}
};
变态跳台阶
题目描述：
一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
算法思路：
f(1)=1; f(2)=2; 当n=3时：
- 第一种方法：一次性跳3阶；
- 第二种方法：先跳上2阶（这2阶想怎么跳就怎么跳），再一次性跳1阶，就是f(2)
- 第三种方法：先跳上1阶，再一次性跳2阶，就是f(1); 综上：f(3)=f(2)+f(1)+1
当n=4时：
- 第一种方法：一次性跳4阶；
- 第二种方法：先跳上3阶（这3阶想怎么跳就怎么跳），再一次性跳1阶，就是f(3)
- 第三种方法：先跳上2阶（这2阶想怎么跳就怎么跳），再一次性跳2阶，就是f(2);
- 第四种方法：先跳上1阶，再一次性跳3阶，就是f(1) 综上：f(4)=f(3)+f(2)+f(1)+1
当n=5时：
- 第一种方法：一次性跳5阶；
- 第二种方法：先跳上4阶（这4阶想怎么跳就怎么跳），再一次性跳1阶，就是f(4)
- 第三种方法：先跳上3阶（这3阶想怎么跳就怎么跳），再一次性跳2阶，就是f(3);
- 第四种方法：先跳上2阶（这2阶想怎么跳就怎么跳），再一次性跳3阶，就是f(2)
- 第五种方法：先跳上1阶，再一次性跳4阶，就是f(1)
综上：f(5)=f(4)+f(3)+f(2)+f(1)+1
…………………..
于是:
f(n) = f(n-1)+f(n-2)+…+f(n-(n-1)) + 1 => f(1) + f(2) + f(3) + … + f(n-1)+1
代码（牛客网，循环来说，存在一个number里面）
class Solution {
public:
int jumpFloorII(int number) {
int i,j;
vector<int>a;
a.push_back(0);
a.push_back(1);
a.push_back(2);
int sum=0;
int one=1,two=2;
int temp=0;
if(number<=0)
{
return 0;
}
if(number==1)
{
return 1;
}
if(number==2)
{
return 2;
}
for(j=0;j<(number-2);j++)
{
for(i=0;i<a.size();i++)
{
temp=temp+a[i];
}
a.push_back((temp+1));
temp=0;
}
/*for(i=0;i<a.size();i++)
{
sum=sum+a[i];
}
*/
return a[number];
}
};
矩形覆盖
题目描述：
我们可以用21的小矩形横着或者竖着去覆盖更大的矩形。请问用n个21的小矩形无重叠地覆盖一个2*n的大矩形，总共有多少种方法？
算法思路：
跟跳台阶这道题一样，你要么横着去覆盖，要么竖着去覆盖
- 如果竖着去覆盖，那么剩下的区域可以随便覆盖，只要覆盖满就行
- 如果横着去覆盖，那么必须横着放两块，组成一个“田”，剩下的区域在去随便怎么覆盖 这是典型的斐波那契数列
代码（牛客网）：
class Solution {
public:
int rectCover(int number) {
int i,k=87;
int one=1;
int two=2;
int temp1,temp2;
if(number==0)
{
return 0;
}
if(number==1)
{
return 1;
}
if(number==2)
{
return 2;
}
else{
for(i=2;i<number;i++)
{
temp1=one+two;
one=two;
two=temp1;
}
}
return temp1;
}
};
